CSE 5311 Section 501 Fall 1998
Homework 6
Due: April 15, 1998, in class
Iteration 0: vertex = 1 2 3 4 5 d = 0 inf inf inf inf pred = nil nil nil nil nil Q = { 1 2 3 4 5 } Iteration 1: vertex = 1 2 3 4 5 d = 0 3 inf 5 inf pred = nil 1 nil 1 nil Q = { 2 3 4 5 } Iteration 2: vertex = 1 2 3 4 5 d = 0 3 9 5 inf pred = nil 1 2 1 nil Q = { 3 4 5 } Iteration 3: vertex = 1 2 3 4 5 d = 0 3 9 5 11 pred = nil 1 2 1 4 Q = { 3 5 } Iteration 4: vertex = 1 2 3 4 5 d = 0 3 9 5 11 pred = nil 1 2 1 4 Q = { 5 } Iteration 5: vertex = 1 2 3 4 5 d = 0 3 9 5 11 pred = nil 1 2 1 4 Q = { } Iteration 0: vertex = 1 2 3 4 5 d = inf inf inf inf 0 pred = nil nil nil nil nil Q = { 1 2 3 4 5 } Iteration 1: vertex = 1 2 3 4 5 d = 3 inf 7 inf 0 pred = 5 nil 5 nil nil Q = { 1 2 3 4 } Iteration 2: vertex = 1 2 3 4 5 d = 3 6 7 8 0 pred = 5 1 5 1 nil Q = { 2 3 4 } Iteration 3: vertex = 1 2 3 4 5 d = 3 6 7 8 0 pred = 5 1 5 1 nil Q = { 3 4 } Iteration 4: vertex = 1 2 3 4 5 d = 3 6 7 8 0 pred = 5 1 5 1 nil Q = { 4 } Iteration 5: vertex = 1 2 3 4 5 d = 3 6 7 8 0 pred = 5 1 5 1 nil Q = { }
Iteration 1: vertex = 1 2 3 4 5 d = 2 998 7 inf 0 pred = 5 3 5 nil nil Iteration 2: vertex = 1 2 3 4 5 d = 2 5 6 9 0 pred = 5 3 4 1 nil Iteration 3: vertex = 1 2 3 4 5 d = 2 4 6 9 0 pred = 5 3 4 1 nil Iteration 4: vertex = 1 2 3 4 5 d = 2 4 6 9 0 pred = 5 3 4 1 nil Iteration 1: vertex = 1 2 3 4 5 d = 0 6 4 7 2 pred = nil 1 4 1 2 Iteration 2: vertex = 1 2 3 4 5 d = 0 2 4 7 2 pred = nil 3 4 1 2 Iteration 3: vertex = 1 2 3 4 5 d = 0 2 4 7 -2 pred = nil 3 4 1 2 Iteration 4: vertex = 1 2 3 4 5 d = 0 2 4 7 -2 pred = nil 3 4 1 2 Iteration 1: vertex = 1 2 3 4 5 d = 2 998 4 inf 0 pred = 5 3 5 nil nil Iteration 2: vertex = 1 2 3 4 5 d = 2 2 4 9 0 pred = 5 3 5 1 nil Iteration 3: vertex = 1 2 3 4 5 d = 0 2 2 9 -2 pred = 5 3 5 1 2 Iteration 4: vertex = 1 2 3 4 5 d = 0 0 2 7 -2 pred = 5 3 5 1 2 Detected negative weight cycle. Iteration 1: vertex = 1 2 3 4 5 d = 0 6 4 7 2 pred = nil 1 4 1 2 Iteration 2: vertex = 1 2 3 4 5 d = 0 2 4 7 2 pred = nil 3 4 1 2 Iteration 3: vertex = 1 2 3 4 5 d = 0 2 2 7 -2 pred = nil 3 5 1 2 Iteration 4: vertex = 1 2 3 4 5 d = 0 0 2 7 -2 pred = nil 3 5 1 2 Detected negative weight cycle.
The proof of Lemma 25.12 shows that for every v, d[v] has attained its final value after length(any shortest-weight path to v) iterations of Bellman-Ford. Thus after m passes, Bellman-Ford can terminate. We do not know m in advance, so we can not make the algorithm loop exactly m times and then terminate. However, if we make the algorithm stop when nothing changes any more, it will stop after m+1 iterations (after one iteration that makes no changes).
New-Bellman-Ford(G, w, s) Initialize-Single-Source(G,s) changes = true while changes = true changes = false for each edge (u,v) in E[G] Relax-M(u,v,w) Relax-M(u,v,w) if d[v] > d[u] + w(u,v) then d[v] = d[u] + w(u,v) pi[v] = u changes = true
The test for a negative-weight cycle (based on the existence of a d value that would change if another relaxation step were done) has been removed above, because this version of the algorithm will never get out of the while loop unless all ds stop changing.
Here are two ways to detect negative-weight cycles:
Suppose a maximum flow for G has been computed, and a new edge with capacity 1 is added to E. Describe how the maximum flow can be efficiently updated. It is not the value of the flow that must be updated, but the flow itself. Analyze the run time of your algorithm.
Execute one iteration of the Ford-Fulkerson algorithm. The new edge in E adds a new edge to the residual graph, so look for an augmenting path and update the flow if a path is found.
Time: O(V + E) = O(E) if a path is found with depth-first or breadth-first search.
Only 1 iteration is needed because adding the capacity-1 edge increases the capacity of the min cut by at most 1. Thus the max flow (equal to the min cut capacity) increases by at most 1. Since all edge capacities are 1, any augmentation increases flow by 1, so only 1 augmentation can be needed.
Initialize-Single-Source(G,s) for each vertex v in V[G] d[v] = infinity pi[v] = nil d[s] = 0 Relax(u,v,w) if d[v] > d[u] + w(u,v) then d[v] = d[u] + w(u,v) pi[v] = u Bellman-Ford(G,w,s) 1. Initialize-Single-Source(G,s) 2. for i = 1 to |V[G]| - 1 3. for each edge (u,v) in E[G] 4. Relax(u,v,w) 5. for each edge (u,v) in E[G] 6. if d[v] > d[u] + w(u,v) 7. then return {\sc false} 8. return true
What is the running time, the speedup, and the efficiency of the parallel algorithm?
The serial run time of the Bellman-Ford algorithm is O(VE). If the loops are run in parallel and the number of processors P is at least , then the parallel algorithm runs in time O(V), which results in a speedup S of O(VE)/O(V) = E and an efficiency E of V/P.
Diane J. Cook