CSE 5311 Fall 1999

Quiz #9

1.

(14 points.) Compute the shortest paths to all vertices from start vertex a in the graph below using Dijkstra's algorithm and the Bellman-Ford algorithm. For Dijkstra's algorithm, show the updated priority queue after each step. For the Bellman-Ford algorithm, show the updated shortest distances after each iteration. Break ties alphabetically.

Dijkstra's Algorithm
   Q = {(a, 0, nil), (b, inf, nil), (c, inf, nil), (d, inf, nil), (e, inf, nil)}
   Extract (a, 0, nil)
   Q = {(b, 5, a), (c, 3, a), (d, inf, nil), (e, inf, nil)}
   Extract (c, 3, a)
   Q = {(b, 4, c), (d, 5, c), (e, 6, c)}
   Extract (b, 4, c)
   Q = {(d, 5, c), (e, 5, b)}
   Extract (d, 5, c)
   Q = {(e, 5, b)}
   Extract (e, 5, b)

Bellman-Ford Algorithm
   Initial values
   (a, 0, nil), (b, inf, nil), (c, inf, nil), (d, inf, nil), (e, inf, nil)
   Check edges (a,b), (a,c), (b,e), (c,b), (c,d), (c,e), (d,e)
   After iteration 1
   (a, 0, nil), (b, 5, a), (c, 3, a), (d, inf, nil), (e, inf, nil)
   After iteration 2
   (a, 0, nil), (b, 4, c), (c, 3, a), (d, 5, c), (e, 6, b)
   After iteration 3
   (a, 0, nil), (b, 4, c), (c, 3, a), (d, 5, c), (e, 5, b)
   After iteration 4
   (a, 0, nil), (b, 4, c), (c, 3, a), (d, 5, c), (e, 5, b)
   No negative weight cycles

2.

(6 points.) Give an example of a graph where Bellman-Ford will provide a correct answer and Dijkstra will not provide a correct answer.

G = ({a,b,c,d}, {(a,b,2), (a,c,4), (b,d,1), (c,b,-3)}
Node a is the source (cost 0), Q = {(b,2,a), (c,4,a), (d,inf,nil)}.
Remove b (cost 2), Q = {(c,4,a), (d,b,1)}.
Remove d (cost 3), Q = {(c,4,a)} .
Remove c (cost 4), Q = {}.
Dijkstra's algorithm finds a path from a to b of a->b with cost 2.
The shortest path from a to b is actually a->c->b with cost 1.