Suppose that you have a directed graph G= (V; E) with an edge weight function w

Question

Suppose that you have a directed graph

G= (V; E) with an edge weight function w and a source vertex s (element of) V.

The weights can be negative, but there are no negative weight cycles.

Furthermore, assume that all edge weights are distinct (i.e. no two edges have the same

weight). The single source shortest path problem is to nd the shortest path distances from s to every vertex in V.

(a)

Suppose that you also guaranteed that for all v (element of) V, a shortest path from s to v has

increasing edge weights. Give an algorithm to nd the shortest path distances from

s to every vertex in V. Analyze the running time of your algorithm and explain why it is

correct. For full credit, your algorithm should run in time

O(V+ElogE).

(b)

A sequence is bitonic if it monotonically increases and then monotonically decreases, or

if by a circular shift it monotonically increases and then monotonically decreases. For

example the sequences (1;4;6;8;3;2), (9;2;4;10;5), and (1;2;3;4) are bitonic,

but (1;3;12;4;2;10) is not bitonic. Now, suppose that the sequences of edge weights

along the shortest paths are no longer guaranteed to be increasing, but instead are

guaranteed to be bitonic. Give a single source shortest path algorithm, explain why it is

correct, and analyze its running time. For full credit, your algorithm should run in time

O(V+ElogE).

Explanation / Answer

a) dijikstra's algorithm
Dijikstra's algorithm extracts minimum each time, if this extraction is done via priority wueue, then
In this case, EXTRACT_MIN operations takes O(lg E) time and there are |V| such operations.
The binary heap can be build in O(V) time.
Operation DECREASE (in the RELAX) takes O(lg E) time and there are at most such operations.
Hence, the running time of the algorithm with binary heap provided given graph is sparse is O(V + E lg E).

b) bitonic sequence, can be considered of comprising of all edges from u to v, where u<v .... thus we can go to maximum number by using shortest path algo to terminating end... and this shortest path algo is given by Dijikstra's, whose time complexity is O(V + ElgE) as explained above

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.