28.2 Shortest Paths on DAGs

Recall from the previous section that DAGs are directed, acyclic graphs. If we wanted to find the shortest path on DAGs we could use Dijkstra's. However, with DAGs there's a simple shortest path algorithm which also handles negative edge weights!

Dijkstra's Negative Edge Weight Failure

Recall that Dijkstra's can fail if negative edges exist because it relies on the assumption that once we visit an edge, we've found the shortest path to that edge. But if negative edge weights can exist ahead of where we can see, then this assumption fails. Consider the following example:

Starting from A, Dijkstra's will visit C first, then B (never even considering the edge B→C¹

Of course, negative edge weights do not mean Dijkstra's is guaranteed to fail. Dijkstra's succeeds with the following example:

¹. This technically depends on your implementation of Dijkstra's. If we ensure that the relaxation step only considers neighbors that are still in the queue (haven't been visited yet), then it is true that B→C will never be considered. If you don't have that check, then technically when we pop the last node (B) from the queue, we'd consider B's neighbors and update C which gives us the right answer for this specific example. However, in that case one could argue that the graph breaks the Dijkstra invariant and thus Dijkstra has 'failed'. Note, the Dijkstra invariant: once a node is deleted from the queue (visited) then you've found the shortest path to that node. ↩

Shortest Path Algorithm for DAGs

Visit vertices in topological order:

• On each visit, relax all outgoing edges

Recall the definition for relaxing an edge u→v with weight w:

if distTo[u] + w < distTo[v]:
    distTo[v] = distTo[u] + w
    edgeTo[v] = u

Since we visit vertices in topological order, a vertex is visited only when all possible info about it has been considered. This means that if negative edge weights exist along a path to v, then those have been taken into account by the time we get to �v!

Finding a topological sort takes O(V+E) time while relaxation from each vertex also takes O(V+E) time in total. Thus, the overall runtime is O(V+E). Recall that Dijkstra's takes O((V+E)logV) time because of our min-heap operations.

What if we want to solve the shortest path problem on graphs that aren't DAGs and also may have negative edges? An extension of Dijkstra's called Bellman Ford can suit your needs, though it is out of scope for this course.