Finds shortest paths from a source to all other vertices in a weighted graph (non-negative weights). Uses a min-heap priority queue.
import heapq
from collections import defaultdict
defdijkstra(graph, src):
dist = defaultdict(lambda: float('inf'))
dist[src] = 0
heap = [(0, src)] # (distance, node)while heap:
d, u = heapq.heappop(heap)
if d > dist[u]: continue# stale entryfor v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
return dist # O((V + E) log V)
Dijkstra’s fails with negative edge weights. Use Bellman-Ford O(VE) for negative weights.
Minimum Spanning Tree
An MST connects all vertices with minimum total weight and no cycles. Two classic algorithms:
Algorithm
Strategy
Complexity
Best for
Kruskal’s
Sort edges, add if no cycle (Union-Find)
O(E log E)
Sparse graphs
Prim’s
Grow tree: always add cheapest edge to unvisited node (heap)
O(E log V)
Dense graphs
Bellman-Ford
Relaxes all edges V-1 times. Handles negative weights and detects negative cycles.
defbellman_ford(vertices, edges, src):
dist = {v: float('inf') for v in vertices}
dist[src] = 0for _ inrange(len(vertices)-1): # V-1 passesfor u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
return dist # O(VE)
Practice
1. Why does Dijkstra's fail on negative edges?
Dijkstra's marks a node "done" when it's popped from the heap,
assuming the current distance is final. With negative edges, a later
path via a negative edge could give a shorter distance — but the
node is already "done" and won't be re-evaluated.
2. Give a real-world use case for MST and one for Dijkstra's.
MST: laying power lines / network cable to connect all buildings
with minimum total wire length (Kruskal's / Prim's).
Dijkstra's: GPS navigation — find the fastest route from your location
to a destination (each road has a travel-time weight).
Correct — greedy: extend the shortest known path at each step.
Bellman-Ford detects negative cycles.
Topo sort is for DAGs, not weighted shortest path.
Recap: Dijkstra's is greedy — always relax the closest unvisited vertex. The min-heap efficiently retrieves it in O(log V).
Dijkstra's fails when the graph has
Dijkstra's scales to millions of vertices with a good heap.
Correct — a shorter path through a negative edge might be missed after a node is 'closed'.
Dijkstra's handles cycles correctly via the 'stale entry' check.
It just won't reach the other component; that's not a failure, just unreachable nodes.
Recap: Dijkstra's assumes once a node is settled, its distance is final. Negative edges violate this assumption. Use Bellman-Ford instead.
Kruskal's MST algorithm works by
That's Prim's algorithm.
Correct — uses Union-Find to check cycle in near-O(1).
BFS is not part of Kruskal's.
That's Bellman-Ford.
Recap: Kruskal's = sort edges, greedily add cheapest edge that connects two different components (Union-Find). O(E log E).
Bellman-Ford runs V-1 iterations because
The number of edges is E, not V-1.
Correct — any simple path visits at most V vertices and thus V-1 edges.
Bellman-Ford relaxes ALL edges in each of V-1 iterations.
Load factor is a hash table concept.
Recap: V-1 passes guarantees all paths of length up to V-1 edges are correctly computed. A V-th pass that still relaxes an edge indicates a negative cycle.
An MST of a graph with V vertices has
V edges would create a cycle.
Correct — spanning tree on V vertices always has exactly V-1 edges.
MST uses only a subset of edges — the minimum needed to connect all vertices.
Not a standard formula.
Recap: MST = spanning tree = V vertices + V-1 edges + no cycles + all vertices reachable. 'Minimum' means minimum total weight.