Question

Problem 6 (20 points). Let G- (V,E) be a directed Let E' be another set of edges on V with edge length '(e) >0 for any e EE. Let s,t EV. Design an algorithm runs in O(lV+ E) time to find an edge e'e E' whose addition to G will result in the maximum decrease of the distance from s to t. Explain why your algorithms runs in O(V2+E') time. graph with edge length l(e) >0 for any e E E.

Answer 1

Algorithm for (O|V|2 + |t|n)

Approach:

1. We can use Ford - Bellman algorithm with dome modifications.

2. First Create a single dimensional array D[] to store shortest path from node s to some node t.

3. Initially we can say D[s] = 0 and all other D[I] = +oo(infinity).

4. Now when we iterate through all edges k times and relax them, then D[u] holds the shortest path value from node s to t after <= v edges.

Please find below Pseudocode:-

For each vertex v in vertices

D[v] : =+oo

D[s] = 0

repeat V times

for each edge (u, v) with weight w in edges

if (D[u] + W < D[v]:

D[v] = D[u] + W