DAG shortest paths by topological-order relaxation
When the road network has no cycles at all — every road points 'forward' and you can never return to a city you have left — the shortest-path problem becomes wonderfully easy. You can line all the cities up in an order where every road goes left to right, then process them strictly in that order. By the time you reach a city, every route into it has already been considered, so its distance is final. No priority queue, no repeated passes; one sweep is enough.
The graph must be a DAG (directed acyclic graph). First compute a topological ordering — a linear arrangement of the vertices such that every edge goes from an earlier vertex to a later one (possible exactly because there are no cycles). Then process vertices in that order, and for each one relax all its outgoing edges. Why does a single pass suffice? When you process vertex u, every vertex with an edge into u came earlier in the order and has already been processed, so d[u] is already final before you ever use it. This is the topological-order invariant: distances are finalized strictly left to right. The cost is O(V + E) — linear — counting the topological sort plus one relaxation of each edge.
DAG shortest paths show up in project scheduling (tasks with prerequisites), critical-path analysis in build systems and spreadsheets, and dynamic programming on a DAG of subproblems — in fact many DP recurrences ARE exactly this algorithm in disguise. The beautiful bonus: because the order, not the sign of weights, guarantees correctness, this method handles NEGATIVE edge weights with no trouble, and you can find LONGEST paths just by flipping the comparison. The only requirement is acyclicity; the moment a cycle exists, no valid topological order exists and you must fall back to Dijkstra or Bellman-Ford.
Tasks a->b (3), a->c (2), b->d (1), c->d (5). Topological order a, b, c, d. Process a: d[b]=3, d[c]=2. Process b: d[d]=3+1=4. Process c: d[d]=min(4, 2+5)=4. Process d: nothing. dist(d)=4, found in one left-to-right sweep — and the same method gives the LONGEST path (critical path) if you maximize instead.
In topological order every predecessor is finalized before a vertex is used, so one pass settles all distances in O(V+E).
This linear-time method only works on DAGs. Unlike Dijkstra it tolerates negative weights, but a single directed cycle makes a topological order impossible and forces you to use Bellman-Ford instead.