Shortest paths quiz
Let e = v → w be an edge with weight 17.0. Suppose that during the generic shortest paths algorithm, distTo[v] = ∞ and distTo[w] = 15.0. What will distTo[w] be after calling relax(e)?
the program will encounter a Java runtime exception
15.0
17.0
∞
Submit
What is the order of growth of Dijkstra's algorithm if we use an ordered array for the PQ? Assume there are no self-edges or parallel edges.
V
E
V
2
E log V
EV
Submit
Given a graph where every vertex is reachable from v, how do our three shortest paths algorithms (Dijkstra's, Topological-Sort-based, Bellman-Ford) differ when using v as the source?
The order in which edges are relaxed.
The number of times each edge is relaxed.
The set of edges that are relaxed at least once.
Submit