Shortest Paths:Negative Cost CyclesNegativecostcycleObservation. If some path from s to t contains a negative cost cyclethere does not exist a shortest s-t path; otherwise, there exists onethatis simple.Wc(W)<0chapter25
chapter25
Shortest Paths: Dynamic ProgramminoDef. OpT(i, v)=length of shortest s-v path P using at mostiedges.Case1:P uses atmosti-1edgesOPT(i, v) = OPT(i-1, v)Case 2: Puses exactly I edges. If (w, v) is the last edge, then OpT use the best s-w path using at most i-1edges and edge (w, v).ifi-oOOPT(i,V)min OPT(i-I, v),1OPT(i-1,W)+Cotherwisemin(v,W)EESVWRemark: if no negative cycles, then OPT(n-1, v)=length of shortest s-v pathchapter25
Shortest Paths: Dynamic Programming Def. OPT(i, v)=length of shortest s-v path P using at most i edges. • Case 1: P uses at most i-1 edges. − OPT(i, v) = OPT(i-1, v) • Case 2: P uses exactly I edges. − If (w, v) is the last edge, then OPT use the best s-w path using at most i-1 edges and edge (w, v). Remark: if no negative cycles, then OPT(n-1, v)=length of shortest s-v path. s w v chapter25
Shortest Paths: implementationShortest-Path(G, t) {foreach node v EVM[O, V] = 00M[O, t] = 0for i = 1 to n-1for each node v e vM[i, v] = M[i-1, v]for each edge (v, w) EM[i, v] = min ( M[i, v], M[i-1, w] + cwy ]3Analysis. @(mn) time, @(n2) space.Finding the shortest paths. Maintain a "successor" for eachtable entry.chapter25
Shortest Paths: implementation Shortest-Path(G, t) { for each node v V M[0, v] = M[0, t] = 0 for i = 1 to n-1 for each node v V M[i, v] = M[i-1, v] for each edge (v, w) E M[i, v] = min { M[i, v], M[i-1, w] + cwv } } Analysis. (mn) time, (n2) space. Finding the shortest paths. Maintain a "successor" for each table entry. chapter25
Theorem: (hard) after the i-th iteration, the costobtained is at most the cost of a shortest path from sto any node v containing at most i edgesProof: We prove it by induction on i.The theorem is true for i-1The shortest path from s to v containing at most one edge is the the edge(s, v) (if exists).Assume that the theorem is true for i-k. Then we are going to show thatthetheoremistruefori-k+1Let P: s-> Vi-> V2 ... ->Vm-> v be the shortest path from s to v containingatmost k+1 edges. Then P1: s-> Vi-> V2 .. ->Vm must be the shortestpath from s to Vm containingat most k edges. By assumption, P1 hasbeen obtained after (k)-th iteration. In the (k+1)-th iteration, we triedto RELAX(Vm, V, w) on node Vm. Thus, path P is obtained after the(k+1)-th iteration.chapter25
Theorem: (hard) after the i-th iteration, the cost obtained is at most the cost of a shortest path from s to any node v containing at most i edges. Proof: We prove it by induction on i. The theorem is true for i=1. The shortest path from s to v containing at most one edge is the the edge (s, v) (if exists). Assume that the theorem is true for i=k. Then we are going to show that the theorem is true for i=k+1. Let P: s-> v1 -> v2 .->vm-> v be the shortest path from s to v containing at most k+1 edges. Then P1: s-> v1 -> v2 .->vm must be the shortest path from s to vm containing at most k edges. By assumption, P1 has been obtained after (k)-th iteration. In the (k+1)-th iteration, we tried to RELAX(vm, v, w) on node vm. Thus, path P is obtained after the (k+1)-th iteration. chapter25
Shortest Paths: Practical implementationsPractical improvements Maintain only one array M[v] = shortest v-t path that wehavefound so far.No need to check edges of the form (v, w) unless M[w]changed in previous iteration.Theorem. Throughout the algorithm, M[v] is length of somes-v path, and after i rounds of updates, the value M[vl is nolarger than the length of shortest s-v path using ≤ i edgesOverall impact.Memory: O(m + n)Running time: O(mn) worst case, but substantially faster inpractice.chapter25
Shortest Paths: Practical implementations Practical improvements. • Maintain only one array M[v] = shortest v-t path that we havefound so far. • No need to check edges of the form (v, w) unless M[w] changed in previous iteration. Theorem. Throughout the algorithm, M[v] is length of some s-v path, and after i rounds of updates, the value M[v] is no larger than the length of shortest s-v path using i edges. Overall impact. • Memory: O(m + n). • Running time: O(mn) worst case, but substantially faster in practice. chapter25