DSA: Graphs, Shortest Path Algorithms
Learn Dijkstra, Bellman-Ford, Floyd-Warshall, BFS-based shortest paths, and advanced techniques like 0-1 BFS and multi-source BFS.
Shortest Path Algorithm Comparison
No single shortest path algorithm fits every situation. The right choice depends on whether the graph is weighted or unweighted, whether negative weights exist, and whether you need single-source or all-pairs distances.
Choosing the Right Algorithm
Match the algorithm to the graph's properties. Using Dijkstra on a graph with negative weights produces incorrect results.
- BFS: unweighted graphs O(V + E)
- Dijkstra: non-negative weighted graphs O(E log V) with a heap
- Bellman-Ford: graphs with negative weights, detects negative cycles, O(VE)
- Floyd-Warshall: all-pairs shortest paths, dense graphs O(V³)
| Algorithm | Negative Weights | Source Type | Time |
|---|---|---|---|
| BFS | No (unweighted only) | Single source | O(V + E) |
| Dijkstra | No | Single source | O(E log V) |
| Bellman-Ford | Yes | Single source | O(VE) |
| Floyd-Warshall | Yes (no negative cycles) | All pairs | O(V³) |
| DAG Shortest Path | Yes | Single source | O(V + E) |
| 0-1 BFS | No (weights 0 or 1 only) | Single source | O(V + E) |
Shortest Path in Unweighted Graph (BFS)
BFS naturally finds the shortest path in an unweighted graph because it explores nodes level by level. The first time a node is reached, it is via the fewest edges possible.
BFS Distance Array
Maintain a dist[] array initialised to -1. When a node is first enqueued, set dist[v] = dist[u] + 1.
- Initialise dist[src] = 0, all others = -1
- On first visit to neighbour v from u: dist[v] = dist[u] + 1
- BFS level = edge count from source = shortest path in unweighted graph
- To reconstruct the path, maintain a parent[] array alongside dist[]
BFS Shortest Path (Unweighted)
C++dist[v] = -1 acts as both the unvisited marker and the guard that prevents re-enqueuing. First visit always gives the shortest distance.
Dijkstra's Algorithm
Dijkstra finds the shortest path from a single source to all vertices in a graph with non-negative edge weights. A min-heap priority queue always processes the nearest unvisited node next.
Dijkstra's Greedy Strategy
Always relax the node with the smallest known distance first. Once a node is popped from the priority queue, its distance is finalised.
- Initialise dist[src] = 0, all others = infinity
- Push (dist, node) pairs into a min-heap
- On pop: skip if the popped distance is outdated (already improved)
- Relax all neighbours: if dist[u] + w < dist[v], update dist[v] and push to heap
Dijkstra's Algorithm with Min-Heap
C++The stale-entry skip (d > dist[u]) handles multiple insertions of the same node into the heap without a decrease-key operation.
Bellman-Ford Algorithm
Bellman-Ford relaxes all edges V-1 times. After V-1 passes, distances to all reachable vertices are finalised. A Vth pass that still improves any distance confirms a negative weight cycle.
Bellman-Ford Key Properties
V-1 relaxation passes are sufficient because the longest simple path in a V-vertex graph has at most V-1 edges.
- Works with negative edge weights (unlike Dijkstra)
- Detects negative cycles: if any distance improves in the Vth pass, a negative cycle exists
- Time: O(VE), slower than Dijkstra but handles more general graphs
- Used in network routing protocols (e.g. distance-vector routing / RIP)
Bellman-Ford with Negative Cycle Detection
C++After V-1 passes, all shortest paths are found. A Vth pass that still relaxes any edge reveals a reachable negative cycle.
Floyd-Warshall Algorithm
Floyd-Warshall computes shortest paths between every pair of vertices in O(V³). For each intermediate vertex k, it checks whether routing through k improves the current known distance between every pair (i, j).
All-Pairs Shortest Path
dist[i][j] is iteratively improved by considering each vertex as a potential intermediate stop on the path from i to j.
- Initialise dist[i][j] = weight of edge (i,j), INF if no edge, 0 if i == j
- Triple loop: for k from 0 to V-1, for every pair (i,j): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
- Negative cycle present if dist[i][i] becomes negative for any i
- Time: O(V³), Space: O(V²), practical only for small or dense graphs
Floyd-Warshall All-Pairs Shortest Paths
C++The k loop picks each vertex as a potential relay. After all V iterations, dist[i][j] holds the true shortest path between every pair.
Shortest Path in a DAG
A DAG's topological order guarantees that when a node is processed, all nodes that can reach it have already been processed. One relaxation pass in topological order computes single-source shortest paths in O(V + E), even with negative weights.
Topo Order + Single Relaxation Pass
Process vertices in topological order. When processing u, relax all its outgoing edges. Since u's distance is already final, every relaxation is correct.
- Topological sort first: O(V + E)
- Initialise dist[src] = 0, all others = infinity
- Iterate in topological order: for each u, relax all edges from u
- Works with negative weights (no negative cycles possible in a DAG)
DAG Shortest Path via Topological Sort
C++Processing in topological order guarantees dist[u] is final before we relax u's edges. Negative weights are safe because DAGs have no cycles.
0-1 BFS
When edge weights are only 0 or 1, a deque replaces the priority queue. Weight-0 edges push the neighbour to the front (same level as the current node); weight-1 edges push to the back. This gives O(V + E) instead of Dijkstra's O(E log V).
Deque-Based BFS for 0-1 Weights
A weight-0 edge does not increase the distance, so the neighbour belongs to the current level (front of deque). A weight-1 edge moves to the next level (back of deque).
- Weight-0 edge: push_front (neighbour at same BFS level)
- Weight-1 edge: push_back (neighbour one level deeper)
- The front of the deque always holds the node with the minimum current distance
- Used in grid problems where some moves are free and others cost 1
0-1 BFS with Deque
C++push_front for weight-0 keeps the deque ordered by distance without a heap. The front always holds the nearest unprocessed node.
Multi-Source BFS
Multi-source BFS finds the shortest distance from any one of multiple source nodes to every other node. Instead of running BFS separately from each source, enqueue all sources simultaneously with distance 0 and run a single BFS.
Simultaneous Multi-Source Start
Enqueuing all sources at distance 0 is equivalent to adding a virtual super-source connected to every real source with a weight-0 edge.
- Push all source nodes into the queue with dist = 0 before the loop
- A single BFS pass computes the distance from the nearest source to every node
- Used in: nearest gate in a building, nearest city, distance to nearest obstacle in a grid
- Time: O(V + E), same as single-source BFS
Multi-Source BFS
C++Both ends (0 and 6) start at distance 0. Node 3 in the middle is equidistant from both sources at distance 3.
Knowledge Check
1. Dijkstra's algorithm fails when the graph contains:
2. The time complexity of Dijkstra's algorithm with a binary heap priority queue is:
3. Bellman-Ford runs how many relaxation passes over all edges?
4. Floyd-Warshall computes:
5. BFS finds the shortest path in an unweighted graph because:
6. 0-1 BFS uses a deque because:
7. Multi-source BFS is initialised by:
8. Shortest path in a DAG can be computed in O(V + E) using: