DSA · Chapter 28 of 40
Shortest Path Algorithms
For weighted graphs BFS is not enough. Dijkstra's algorithm finds shortest paths from one source when all weights are non-negative, using a min-heap to always expand the closest unfinished vertex — O((V + E) log V).
Bellman-Ford handles negative weights in O(V * E) and detects negative cycles; Floyd-Warshall computes all-pairs shortest paths in O(V^3).
Dijkstra in words
Keep a distance map initialised to infinity, push (0, source) on a heap, and relax each neighbour: if dist[u] + w < dist[v], update and push.
Choosing an algorithm
Unweighted → BFS. Non-negative weights, one source → Dijkstra. Negative weights → Bellman-Ford. All pairs on a small graph → Floyd-Warshall.
Example 1 (python)
import heapq
def dijkstra(g, src):
dist = {v: float('inf') for v in g}
dist[src] = 0
h = [(0, src)]
while h:
d, v = heapq.heappop(h)
if d > dist[v]:
continue
for n, w in g[v]:
if d + w < dist[n]:
dist[n] = d + w
heapq.heappush(h, (dist[n], n))
return dist
g = {'A': [('B', 1), ('C', 4)], 'B': [('C', 2)], 'C': []}
print(dijkstra(g, 'A'))Output
{'A': 0, 'B': 1, 'C': 3}The heap always expands the currently closest vertex.
Example 2 (python)
# Bellman-Ford relaxes every edge V-1 times
edges = [('A', 'B', 1), ('B', 'C', 2), ('A', 'C', 4)]
dist = {'A': 0, 'B': float('inf'), 'C': float('inf')}
for _ in range(2):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
print(dist)Output
{'A': 0, 'B': 1, 'C': 3}Slower than Dijkstra but tolerates negative weights.
Key points
- Dijkstra needs non-negative weights and uses a min-heap.
- Bellman-Ford handles negative edges and detects negative cycles.
- Floyd-Warshall gives all-pairs distances in O(V^3).
- BFS is the right answer when every edge costs the same.
💡 Note: Mention why Dijkstra fails with negative weights: a finalised vertex could still be improved later.