6.006 Q2 Shortest Paths

Front 1

(Spring 2011) Given a graph G = (V, E) with positive edge weights, the Bellman-Ford algorithm and Dijkstra’s algorithm can produce different shortest-path trees despite always producing the same shortest-path weights.

Back 1

True. Both algorithms are guaranteed to produce the same shortest- path weight, but if there are multiple shortest paths, Dijkstra’s will choose the shortest path according to the greedy strategy, and Bellman-Ford will choose the shortest path depending on the order of relaxations, and the two shortest path trees may be different.

Front 2

[Spring 2010] For all weighted graphs and all vertices s and t, Bellman-Ford starting at s will always return a shortest path to t.

Back 2

FALSE. If the graph contains a negative-weight cycle, then no shortest path exists.

Front 3

[Spring 2010] At the termination of the Bellman-Ford algorithm, even if the graph has a negative length cycle, a correct shortest path is found for a vertex for which shortest path is well-defined.

Back 3

TRUE. If the shortest path is well defined, then it cannot include a cycle. Thus, the shortest path contains at most V − 1 edges. Running the usual V − 1 iterations of Bellman-Form will therefore find that path.

Front 4

[Fall 2009] In a graph with negative weight cycles, one such cycle can be found in O(V E) time where V is the number of vertices and E is the number of edges in the graph.

Back 4

True

Front 5

[Fall 2008] Changing the RELAX function to update if d[v] ≥ d[u] + w(u, v) (instead of strictly greater than) may produce different shortest paths, but will not affect the correctness of the Bellman-Ford outputs d and π.

Back 5

False. The parent pointers may not lead back to the source node if a zero-length cycle exists. In the example below, relaxing the (s, a) edge will set d[a] = 1 and π[a] = 1. Then, relaxing the (a, a) edge will set d[a] = 1 and π[a] = a. Following the π pointers from t will no longer give a path to s, so the algorithm is incorrect. (graph in test)

Front 6

[Fall 2008] If a weighted directed graph G is known to have no shortest paths longer than k edges, then it suffices to run Bellman-Ford for only k passes in order to solve the single-source shortest paths problem on G.

Back 6

True. The ith iteration finds shortest paths in G of i or fewer edges, by the path relaxation property (see p. 587 in CLRS).

Front 7

(Spring 2011) Dijkstra’s algorithm may not terminate if the graph contains negative-weight edges.

Back 7

False. It always terminates after |E| relaxations and |V |+|E| priority queue operations, but may produce incorrect results.

Front 8

[Spring 2010] In bidirectional Dijkstra, the first vertex to appear in both the forward and backward runs must be on the shortest path between the source and the destination.

Back 8

FALSE. When a vertex appears in both the forward and backward runs, it may be that there is another vertex (on a different path) which is further away from the source but substantially closer to the destination. (This was covered in recitation.)

Front 9

[Fall 2009] If one transforms edge weights w(u, v) to w′(u, v) = w(u, v) − λ(u) + λ(v) for arbitrary λ(), then Dijkstra on the modified graph will return shortest paths in the original graph.

Back 9

False

Front 10

[Fall 2009] What are the operations required by Dijkstra on the priority queue data structure?

Back 10

EXTRACT _MIN, INSERT and DECREASE_KEY.

Front 11

[Fall 2009] Dijkstra assumes the triangle inequality on edge weights, that is, for each triple of edges (u, v), (u, a) and (a, v), we have w(u, v) >= w(u, a) + w(a, v).

Back 11

False

Front 12

[Spring 2008] If the priority queue in Dijkstra’s algorithm is implemented using a sorted linked list (where the list is kept sorted after each priority queue operation), then Dijkstra’s algorithm would run in O(ElgV +V lgV) time.

Back 12

False. The array can take Θ(V ) time to insert a node, and there are V nodes to insert, for a running time of Ω(V 2) In addition, the Θ(E) calls to decrease-key can each take Θ(V ) time for a total running time of Θ((V + E)V ).

Front 13

[Spring 2010] If all edges in a graph have distinct weights, then the shortest path between two vertices is unique.

Back 13

FALSE. Even if no two edges have the same weight, there could be two paths with the same weight. For example, there could be two paths from s to t with lengths 3 + 5 = 8 and 2 + 6 = 8. These paths have the same length (8) even though the edges (2, 3, 5, 6) are all distinct.

Front 14

[Fall 2008] Let P be a shortest path from some vertex s to some other vertex t in a directed graph. If the weight of each edge in the graph is increased by one, P will still be a shortest path from s to t.

Back 14

False. (counter example in test)

Front 15

How many times does Djikstra perform relaxation on each edge?

Back 15

exactly once.

Front 16

How many times does Bellman-Ford perform relaxation on each edge?

Back 16

|V| - 1

Front 17

What is the relaxation approach?

Back 17

- Maintain distance estimate v.d for each vertex
- Goal: v.d = min(s, v) for each vertex
- Invariant: v.d >= min(s, v)
- Initialization: set v.d = infinity, s.d = 0
-Repeatedly inprove estimates toward goal, by aiming to achieve triangle inequality.

Front 18

Relaxation Algorithm with Shortest Path-Tree:

Back 18

Initialize:
For each V:
v.d = infinity
v.p = None
s.d = 0

while some edge (u, v) has v.d > u.d + w(u, v):
relax(u, v):
if(v.d > u.d + w(u, v)):
v.d = u.d + w(u, v)
v.p = u

Front 19

If a negative-weight cycle is reachable from s, then relaxation can never terminate

Back 19

True

Front 20

Bellman-Ford algorithm time:

Back 20

Polynomial

Front 21

Dijkstra's algorithm time:

Back 21

Nearly linear