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


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
V2
E log V
EV

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.