Shortest paths

Pick a shortest-path method based on the edge costs. If every edge costs the same, use BFS. If edges cost only 0 or 1, use 0-1 BFS with a deque. If no edge is negative, use Dijkstra's algorithm. In a graph with no cycles, process nodes in topological order, even with negative edges. With negative edges in general, use something like Bellman–Ford, and watch for negative cycles.

Dijkstra's algorithm keeps a best-known distance for every node, and always settles the unsettled node with the smallest one. Why is that distance final? Any other route would pass through an unsettled node that's already at least as far. Edges never cost less than zero, so the rest of that route can't bring the total back down S11.

With a binary heap, when you find a shorter route to a node, push a new entry instead of updating the old one. When you pop an entry, skip it if it no longer matches the node's best distance. Don't mark a node as done when you first push it: a later route may still improve it.

For a typical adjacency-list version, a safe bound is O((V + E) log(V + E)) time and O(V + E) extra space, counting the extra heap entries. Tighter bounds you may have seen make extra assumptions about the graph. Give the bound for the version you actually wrote.

Here's why the first route found isn't always final. Take edges S→A costing 10, S→B costing 1, and B→A costing 1. The first route to A costs 10, but the shortest costs 2.

Extra limits can make the state bigger. If you may use only a few edges, reaching a node cheaply with no edges left isn't better than reaching it at more cost with edges to spare. Track enough information, such as (node, edges used). "At most k stops" means at most k + 1 edges.

Practice: LC 743 Network Delay Time, LC 1631 Path With Minimum Effort, LC 1368 Minimum Cost to Make at Least One Valid Path in a Grid, LC 787 Cheapest Flights Within K Stops. In Path With Minimum Effort, a route's cost is its largest single step, not the sum. Check that extending a route still never makes its cost go down.

Check your understanding: What does a distance measure here? Why is a popped node's distance final? Does the state include every resource that changes where you can go next? Is a node unreachable, or just not improved yet?