15. Shortest Path and MST
📋 Jump to TakeawaysThe previous lesson covered BFS for shortest path in unweighted graphs. But what about weighted graphs — where edges have different costs? That's where Dijkstra's and Bellman-Ford come in. And when you need to connect all nodes with minimum total cost, you need a Minimum Spanning Tree.
Dijkstra's Algorithm
Finds the shortest path from one source to all other nodes in a weighted graph with non-negative edges. Uses a min-heap (priority queue) to always process the closest unvisited node.
LeetCode 743 Variant - Network Delay Time
Given a network of nodes and weighted directed edges, find the time it takes for a signal to reach all nodes from a given source.
import (
"container/heap"
"math"
)
// Types needed for Dijkstra and Prim
type Edge struct {
To, Weight int
}
type Item struct {
Dist, Node int // Dist: total distance from source, Node: target node
}
type MinHeap []Item
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].Dist < h[j].Dist }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(Item)) }
func (h *MinHeap) Pop() interface{} {
old := *h
x := old[len(old)-1]
*h = old[:len(old)-1]
return x
}
func dijkstra(graph map[int][]Edge, start int, n int) []int {
dist := make([]int, n)
for i := range dist {
dist[i] = math.MaxInt
}
dist[start] = 0
// Min-heap: (distance, node)
pq := &MinHeap{{0, start}}
heap.Init(pq)
for pq.Len() > 0 {
curr := heap.Pop(pq).(Item)
if curr.Dist > dist[curr.Node] {
continue // already found a shorter path
}
for _, edge := range graph[curr.Node] {
newDist := dist[curr.Node] + edge.Weight
if newDist < dist[edge.To] {
dist[edge.To] = newDist
heap.Push(pq, Item{newDist, edge.To})
}
}
}
return dist
}How it works: start at source with distance 0. Pop the closest node from the heap. For each neighbor, if going through this node is shorter than the best known path, update and push to heap. Repeat until heap is empty.
Time: O((V + E) log V) with a binary heap. The log V comes from heap operations.
Limitation: doesn't work with negative edge weights. If an edge has weight -5, Dijkstra might skip a path that later becomes shorter through the negative edge.
Bellman-Ford Algorithm
Handles negative edge weights. Slower than Dijkstra but more general. Also detects negative cycles. A negative cycle is a loop where the total weight of edges sums to less than zero. If you walk around it, your distance gets shorter every lap — infinitely.
// edges[i] = [from, to, weight]
func bellmanFord(edges [][]int, n, start int) ([]int, bool) {
dist := make([]int, n)
for i := range dist {
dist[i] = math.MaxInt
}
dist[start] = 0
// Relax all edges V-1 times
for i := 0; i < n-1; i++ {
for _, e := range edges {
u, v, w := e[0], e[1], e[2]
if dist[u] != math.MaxInt && dist[u]+w < dist[v] {
dist[v] = dist[u] + w
}
}
}
// Check for negative cycles (one more relaxation)
for _, e := range edges {
u, v, w := e[0], e[1], e[2]
if dist[u] != math.MaxInt && dist[u]+w < dist[v] {
return nil, false // negative cycle exists
}
}
return dist, true
}Time: O(V × E). Slower than Dijkstra, but works with negative weights.
When to use: currency exchange (detect arbitrage = negative cycle), graphs where edges can have negative costs.
LeetCode 787 - Cheapest Flights Within K Stops
Modified Bellman-Ford: relax edges at most K+1 times (K stops = K+1 edges).
// flights[i] = [from, to, price]
func findCheapestPrice(n int, flights [][]int, src, dst, k int) int {
dist := make([]int, n)
for i := range dist {
dist[i] = math.MaxInt
}
dist[src] = 0
for i := 0; i <= k; i++ {
temp := make([]int, n)
copy(temp, dist)
for _, f := range flights {
u, v, w := f[0], f[1], f[2]
if dist[u] != math.MaxInt && dist[u]+w < temp[v] {
temp[v] = dist[u] + w
}
}
dist = temp
}
if dist[dst] == math.MaxInt {
return -1
}
return dist[dst]
}When to Use Dijkstra vs BFS vs Bellman-Ford
| Algorithm | Weights | Negative edges | Negative cycles | Time |
|---|---|---|---|---|
| BFS | Unweighted | N/A | N/A | O(V + E) |
| Dijkstra | Non-negative | ✗ | N/A | O((V+E) log V) |
| Bellman-Ford | Any | ✓ | Detects | O(V × E) |
Decision: unweighted → BFS. Non-negative weights → Dijkstra. Negative weights → Bellman-Ford.
Minimum Spanning Tree
An MST connects all nodes in an undirected weighted graph with the minimum total edge weight. No cycles. Exactly V-1 edges for V nodes.
Graph: MST (total weight = 6):
A —3— B A B
| | | |
2 5 2 1
| | | |
C —1— D C —1— DTwo classic algorithms: Kruskal's and Prim's.
Union-Find
Union-Find tracks connected components. Two operations: Find (which component is this node in?) and Union (merge two components). Used by Kruskal's to detect cycles.
LeetCode 547 - Number of Provinces
type UnionFind struct {
parent, rank []int
}
func NewUnionFind(n int) *UnionFind {
parent := make([]int, n)
for i := range parent {
parent[i] = i
}
return &UnionFind{parent, make([]int, n)}
}
func (uf *UnionFind) Find(x int) int {
if uf.parent[x] != x {
uf.parent[x] = uf.Find(uf.parent[x]) // path compression
}
return uf.parent[x]
}
func (uf *UnionFind) Union(x, y int) {
px, py := uf.Find(x), uf.Find(y)
if px == py {
return
}
if uf.rank[px] < uf.rank[py] {
px, py = py, px
}
uf.parent[py] = px
if uf.rank[px] == uf.rank[py] {
uf.rank[px]++
}
}With path compression and union by rank, both operations are nearly O(1) — technically O(α(n)) which is effectively constant.
Kruskal's Algorithm
Sort all edges by weight. Add edges one by one, skipping any that would create a cycle. Uses Union-Find to detect cycles efficiently.
LeetCode 1584 - Min Cost to Connect All Points
import "sort"
// Uses UnionFind as defined above
// edges[i] = [from, to, weight]
func kruskal(n int, edges [][]int) int {
// Sort edges by weight
sort.Slice(edges, func(i, j int) bool {
return edges[i][2] < edges[j][2]
})
uf := NewUnionFind(n)
totalWeight := 0
edgesUsed := 0
for _, e := range edges {
u, v, w := e[0], e[1], e[2]
if uf.Find(u) != uf.Find(v) { // different components
uf.Union(u, v)
totalWeight += w
edgesUsed++
if edgesUsed == n-1 {
break
}
}
}
return totalWeight
}Time: O(E log E) — dominated by sorting edges.
Prim's Algorithm
Start from any node. Repeatedly add the cheapest edge that connects a visited node to an unvisited node. Uses a min-heap.
LeetCode 1584 - Min Cost to Connect All Points (Prim's approach)
// Uses Edge, Item, and MinHeap as defined in Dijkstra above
func prim(graph map[int][]Edge, n int) int {
visited := make([]bool, n)
pq := &MinHeap{{0, 0}} // start from node 0
heap.Init(pq)
totalWeight := 0
for pq.Len() > 0 {
item := heap.Pop(pq).(Item)
if visited[item.Node] {
continue
}
visited[item.Node] = true
totalWeight += item.Dist
for _, edge := range graph[item.Node] {
if !visited[edge.To] {
heap.Push(pq, Item{edge.Weight, edge.To})
}
}
}
return totalWeight
}Time: O((V + E) log V) — same as Dijkstra.
Kruskal's vs Prim's
| Kruskal's | Prim's | |
|---|---|---|
| Approach | Edge-centric (sort all edges) | Vertex-centric (grow from a node) |
| Best for | Sparse graphs | Dense graphs |
| Data structure | Union-Find | Min-heap |
| Time | O(E log E) | O((V+E) log V) |
For sparse graphs (E ≈ V), Kruskal's is simpler. For dense graphs (E ≈ V²), Prim's is faster.
Practice Problems
| Problem | Difficulty | Link |
|---|---|---|
| Network Delay Time | Medium | LeetCode 743 |
| Cheapest Flights Within K Stops | Medium | LeetCode 787 |
| Min Cost to Connect All Points | Medium | LeetCode 1584 |
| Path with Maximum Probability | Medium | LeetCode 1514 |
| Number of Connected Components | Medium | LeetCode 323 |
| Number of Provinces | Medium | LeetCode 547 |
Key Takeaways
- Dijkstra: shortest path with non-negative weights, uses min-heap, O((V+E) log V)
- Bellman-Ford: shortest path with any weights, detects negative cycles, O(V × E)
- Unweighted → BFS. Non-negative → Dijkstra. Negative → Bellman-Ford
- MST connects all nodes with minimum total edge weight — exactly V-1 edges
- Kruskal's: sort edges, add cheapest that doesn't create a cycle (Union-Find)
- Prim's: grow from a node, always add the cheapest edge to an unvisited node (min-heap)
- Union-Find gives nearly O(1) component queries with path compression + union by rank