Shortest paths
BFS finds the fewest edges. When edges cost different amounts, settle the closest node you have not settled yet, offer its neighbours a shorter route, and repeat.
Problems worked on this page, and more to practise
- 743. Network Delay Time
- 787. Cheapest Flights Within K Stops
- 778. Swim in Rising Water
- 1091. Shortest Path in Binary Matrix
- 1631. Path With Minimum Effort
- 1514. Path with Maximum Probability
- 505. The Maze II
- 1976. Number of Ways to Arrive at Destination
- 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance
- 2290. Minimum Obstacle Removal to Reach Corner
- 1368. Minimum Cost to Make at Least One Valid Path in a Grid
- 2642. Design Graph With Shortest Path Calculator
- 882. Reachable Nodes In Subdivided Graph
Why does Dijkstra fail when an edge is negative?
Dijkstra settles the node with the smallest tentative distance and never looks at it again. That is sound because any other route to that node has to leave through a node already at least that far away, and adding more non-negative edges can only make it worse. A negative edge breaks that last step: a longer route can subtract on the way and come in under a distance already settled. Use Bellman-Ford, which relaxes every edge V minus 1 times and never settles anything early.
When do I use Dijkstra instead of BFS?
BFS answers "fewest edges". It is right only when every edge costs the same, because it settles nodes in the order they are discovered. The moment edges carry different costs, the fewest-edges route and the cheapest route come apart, and you need a heap so the node you settle is the closest one rather than the oldest one. Edges of only 0 and 1 are the exception: a deque with free moves pushed to the front keeps it linear.
Why push a second heap entry instead of updating the old one?
Python’s heapq has no decrease-key. There is no way to find an entry already in the heap and lower it, so the template pushes a new entry whenever a distance falls and leaves the old one where it is. The old entry surfaces later carrying a distance worse than the one on record, and the line "if d > dist[u]: continue" throws it away. Leaving that line out is still correct, and it makes you walk the same node’s edges again every time a stale entry comes up.
What is the cost of Dijkstra with a heap?
O((V + E) log V). Every edge can push at most one entry, so the heap holds O(E) entries, and each push and pop costs log of that, which is within a constant of log V for any graph. Space is O(V) for the distances plus O(E) for the heap. A Fibonacci heap brings it to O(E + V log V) in theory and nobody writes one in an interview.
How do I handle "at most K stops"?
A stop limit breaks the settling argument, because the cheapest route to a node may use too many edges while a dearer one fits. Run Bellman-Ford for K plus 1 rounds instead, and start each round from a copy of the distances the round before it produced. Without the copy, one round can relax two edges in a chain and the count of edges stops meaning anything. The alternative is Dijkstra over states of (node, edges used), which is the same idea with the count in the key.