Dijkstra's Algorithm with Topological Sort

Question

I came across this passage in a textbook:

"If the graph is acyclic, we can improve Dijkstra’s algorithm. Vertices may be selected in topological order since when a vertex is selected, its distance can no longer be lowered, because there are no incoming edges from unknown nodes."

I understand Topological Sort and Dijkstra's algorithm but do not understand how topological order can help speed up Dijkstra's especially when the order is not always unique. (unless its referring to space complexity which doesn't make sense either)

Can someone explain how it improves it and give an example?

Answer 1

You can choose an arbitrary topological sorting and process the vertices in this order.

The time complexity is linear in the size of the graph as there is no need for a priority queue anymore. You can just iterate over all vertices in topological order and compute the distance for them.

It goes like this:

dist = 0 for the start vertex and +inf for the rest
for v in topological order:
     for u in neighbors[v] in reverse graph:
        dist[v] = min(dist[v], dist[u] + weight(u, v))    

The correctness follows from the fact that by the time we reach v, we've already processed all vertices that have an edge to v (by the definition of a topological order).