Let G(V, E) be a graph with positive and negative weights on its edges, but with
ID: 3859507 • Letter: L
Question
Let G(V, E) be a graph with positive and negative weights on its edges, but with no negative cycles. Let s belongs to V. Assume it is known that for every shortest path between every pair of nodes, the number of edges in the path is at most k, but k is not known to you. Suggest a modification of Bellman-Ford algorithm so the running time of the new algorithm is O(km). Prove that your algorithm still finds the shortest path from s to every other node, and the correctness of the bound you provided for the running time. As usual n = |V|, and m = |E|.Explanation / Answer
Bellman - Ford Algorithm
The Bellman- ford algorithm uses relaxation to find single source shortest paths on directed graphs that may contains negative wright edges.
The algorithm will also detect if there are any negative weight cycles.
Bellman-ford(G,w,s)
Initialize- Single-Source(G,s)
for i=1 to |G.V|-1
for each edge (u,v) belongs G.E
RELAX(u,v,w)
for each edge(u,v) belongs G.E
if v.d > u.d+w(u,v)
return FALSE
return TRUE
Initialize-Single-Source (G,S)
for each vertex v belongs G.V
v.d = infinity
v.pi= NIL
s.d=0
RELAX(u,v,w)
if v.d> v.d+w(u,v)
v.d=u.d+w(u,v)
v.pi=u
the run time of the Bellman-Ford Algorithm is O(V+VE+E)=O(VE)
PROOF FOR BELLMAN- FORD ALGORITHM FINDS SHORTEST PATH
Let s belongs V be any vertex
Consider path p= <v0,v1,v2.................vk> from v0=s to vk=v that is a Shortest path with minimum number of edges, no negative cycles.
K<= |V|-1
d( S,VI)= d( S,VI-1)+W(VI-1, VI)
Initially d[v0]=0=d(S,V0) and is unchanged since no negative cycles
After 1 pass through E, we have d[V1]= d( S,VI) because we will relax the edge (v0,v1) in the pass, and this is shortest path
After 2 pass through E, we have d[V2]= d( S,V2), because in the second pass we will ralx the edge (v1,v2)
After I passes through E, we have d[VI]= d( S,VI).
After k<=|V|-1 passes through E, we have d[Vk]= d[V]= d( S,V)
d( S,VI)= d( S,VI-1)+W(VI-1, VI)
Initially d[v0]=0=d(S,V0) and is unchanged since no negative cycles
After 1 pass through E, we have d[V1]= d( S,VI) because we will relax the edge (v0,v1) in the pass, and this is shortest path
After 2 pass through E, we have d[V2]= d( S,V2), because in the second pass we will ralx the edge (v1,v2)
After I passes through E, we have d[VI]= d( S,VI).
After k<=|V|-1 passes through E, we have d[Vk]= d[V]= d( S,V)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.