Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
21 Cards in this Set
- Front
- Back
(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.
|
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.
|
|
[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.
|
FALSE. If the graph contains a negative-weight cycle, then no shortest path exists.
|
|
[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.
|
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.
|
|
[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.
|
True
|
|
[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 π.
|
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)
|
|
[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.
|
True. The ith iteration finds shortest paths in G of i or fewer edges, by the path relaxation property (see p. 587 in CLRS).
|
|
(Spring 2011) Dijkstra’s algorithm may not terminate if the graph contains negative-weight edges.
|
False. It always terminates after |E| relaxations and |V |+|E| priority queue operations, but may produce incorrect results.
|
|
[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.
|
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.)
|
|
[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.
|
False
|
|
[Fall 2009] What are the operations required by Dijkstra on the priority queue data structure?
|
EXTRACT _MIN, INSERT and DECREASE_KEY.
|
|
[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).
|
False
|
|
[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.
|
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 ).
|
|
[Spring 2010] If all edges in a graph have distinct weights, then the shortest path between two vertices is unique.
|
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.
|
|
[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.
|
False. (counter example in test)
|
|
How many times does Djikstra perform relaxation on each edge?
|
exactly once.
|
|
How many times does Bellman-Ford perform relaxation on each edge?
|
|V| - 1
|
|
What is the relaxation approach?
|
- 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. |
|
Relaxation Algorithm with Shortest Path-Tree:
|
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 |
|
If a negative-weight cycle is reachable from s, then relaxation can never terminate
|
True
|
|
Bellman-Ford algorithm time:
|
Polynomial
|
|
Dijkstra's algorithm time:
|
Nearly linear
|