Dijkstra is a greedy shortest path with a min-heap, non-negative weights only, O((V+E) log V). Bellman-Ford handles negative weights and detects negative cycles, O(V·E). Floyd-Warshall gives all-pairs shortest path, O(V³), good for small/dense graphs. 0-1 BFS is a deque-based shortcut when edge weights are only 0 or 1.
Sub-patterns
- A — Single-Source (Dijkstra / Bellman-Ford). Shortest paths from one starting node.
- B — All-Pairs (Floyd-Warshall). Shortest paths between every pair of nodes.
- C — 0-1 BFS. A deque-based shortcut when every edge weight is 0 or 1.
Practice set (7)
- Medium — Network Delay Time, Path with Minimum Effort, Cheapest Flights Within K Stops, Path With Maximum Probability, The Maze II (Premium)
- Hard — Swim in Rising Water (also relevant to Union-Find), Minimum Cost to Make at Least One Valid Path in a Grid
Pending
Single-Source (Dijkstra / Bellman-Ford)
Shortest paths from one starting node — Dijkstra for non-negative weights, Bellman-Ford when negative weights (or cycles) are possible.
Pending
All-Pairs (Floyd-Warshall)
Shortest paths between every pair of nodes at once, O(V³) — good for small/dense graphs.
Pending
0-1 BFS
A deque-based shortcut for shortest paths when every edge weight is only 0 or 1.
Notes from readers
Comments — via GitHub