Why we need topological ordering for finding shortest paths

Question

This question is just for discussing algorithms please and not for proposing algorithms. I saw very similar post to mine, but still the answer explains definitions online for topological ordering.

Suppose we have a DAG (directed acyclic graph). Regarding the problem of finding shortest paths, Dijkstra's and Bellman-Ford algorithms are very popular. While both work with weighted directed graph, Bellman-Ford algorithm can work with negative edges. Dijkstra takes $O(E\log{E})$ while Bellman-Ford algorithm takes $O(EV)$ to execute, where $E$ is the number of edges and $V$ is the number of vertices in graph $G$.

Now here comes my issue, topological ordering works by just numbering the order by which we will visit the vertices of a graph and it works with negative edges as well, so this is a pro over Dijkstra. Because of topological ordering, we speed up shortest path finding to just linear time to $O(E+V)$.

Problem: Could you please simply explain the logic behind introducing topological sorting and how it helps cutting down complexity to just $O(E+V)$?

Answer 1

The shortest path between vertices $A$ and $Z$ (where $A\ne Z$) is the minimum over all edges $A\to B_i$ of the weight of that edge plus the shortest path from $B_i$ to $Z$.

For general graphs, it isn't obvious how to optimize that, because some paths from $B_i$ to $Z$ may pass through $A$.

In a dag, that can't happen, and so there is an easy algorithm: compute and cache the shortest path from each vertex to $Z$ the first time you encounter the vertex, and look up the cached value if you reach the same vertex again. If you use a data structure with $O(1)$ insertion and lookup, such as a hash table, or a simple array if the nodes are identified by consecutive integers, then this runs in $O(E+V)$ time, because you do constant work for each first encounter of a vertex, constant work for each edge, and constant work for each subsequent encounter of a vertex, and there are fewer than $E$ subsequent encounters in total.

You don't need to topologically sort the nodes for that algorithm to work in $O(E+V)$ time. If you happen to know the topological order, then you can use it in a dynamic-programming version of the algorithm, which has the same asymptotic run time but may have smaller constant factors. But it isn't topological sorting that enables a linear-time algorithm; it's the fact that you know the graph is a dag.