Consider the following strategy to solve the single source shortest path problem with edge weights from source s.
1. Replace each edge with weight w by w edges of weight 1 connected by new intermediate nodes
2. Run BFS(s) on the modified graph to find the shortest path to each of the original vertices in the graph.
Which of the following statements is correct?
A
This strategy will not solve the problem correctly.
B
This strategy will only work if the graph is acyclic.
C
This strategy will solve the problem correctly and is as efficient as Dijkstra's algorithm.
D
This strategy will solve the problem correctly but is not as efficient as Dijkstra's algorithm.
Consider the following strategy to convert an undirected graph with negative edge weights to one that does not have negative edge weights.
Let the maximum magnitude negative edge weight in the graph be -k. Then, for each edge in the graph with weight w, update the weight to w+k+1.
Consider the following claim:
To solve the shortest path problem in the original graph, we can run Dijkstra's algorithm on the modified graph and subtract the added weights to get
the original distances.
Which of the following is NOT correct?
A
The claim is true for connected acyclic graphs.
B
The claim is true for all graphs.
C
The claim is not true in general for graphs with cycles.
Adding a weight to each edge increases the weight of a path proportional to the number of edges, so "long"
shortest paths (in terms no of edges) get penalized. In a tree (connected acyclic graph), there is only one path between any pair of
nodes, so the shortest path is invariant.
Suppose you have a directed acyclic graph with n vertices and O(n) edges, all having
nonnegative weights. Running time (in form of n) of an efficient algorithm for finding the shortest path to each
vertex from a single source is
The given conditions allow us to use either the DAG shortest paths algorithm or Dijkstra's. DAG shortest paths runs in \Theta (V+E)=\Theta (n), and Dijkstra's
runs in O((V + E) \log V ), or O(V \log V + E) if using a Fibonacci heap. In either case,
Dijkstra's runs in O(n \log n). DAG shortest paths is faster in this case https://www.cs.bgu.ac.il/~ds182/wiki.files/14-shortest_paths.pdf
S1: Consider two positively weighted graphs G = (V; E; w) and G_0 = (V; E; w_0)
with the same vertices V and edges E such that, for any edge e in E , we have
w_0(e) = w(e)^2 .
For any two vertices u, v in V , any shortest path between u and v in G_0 is also a
shortest path in G .
S2: 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.
S1 is FALSE Assume we have two paths in G as (1) path: u-x-v : 4 with w(u,x)=2,w(x,v)=2 (2)path: u-v:3 with w(u,v)=3. The first one is shorter in G_0 while the second
one is shorter in G.
S2 is FLASE The list can take \Theta (V) time to insert a node, and there are (V) nodes to insert, for a running time of \Omega (V^2). In addition, the \Theta (E) calls to decrease-key can each take \Theta (V) time for a total running time of \Theta ((V + E)V ).
S1: 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.
S2: Dijkstra's algorithm may not terminate if the graph contains negative-weight
S1 is TRUE Both algorithms are guaranteed to produce the same shortestpath 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.
S2 is FLASE It always terminates after |E| relaxations and |V|+|E| priority queue operations, but may produce incorrect results.