11.3 Dijkstra's Shortest Path & Disjoint Set Union (Union-Find)

1. What Are Dijkstra's Algorithm & Union-Find?

1. Dijkstra's Shortest Path Algorithm: Finds the minimum travel cost from a starting node src to every other node in a graph where edges have positive weights (distances/costs).
2. Disjoint Set Union (DSU / Union-Find): A data structure that tracks how N items are grouped into separate islands (connected components) as edges are added one by one, answering "Are A and B in the same group?" and "Merge A's group with B's group" in near O(1) time.

2. Why Do We Need Them & How Do They Work?

Why Plain BFS Fails on Weighted Graphs (And Why Dijkstra Works)

In an unweighted graph, every step costs 1, so a FIFO Queue (BFS) discovers nodes in order of distance. When edges have weights, a direct edge A -> B might cost 100, while a 2-step detour A -> C -> B costs 2 + 3 = 5! Dijkstra's Algorithm replaces the FIFO Queue with a Min-Heap of (distance_so_far, node):

• Always pop the node u with the smallest total distance from src.
• For each neighbor v with edge weight w, check if going through u is a shortcut (dist[u] + w < dist[v]). If yes, update dist[v] and push (dist[v], v) into the Min-Heap!

How Disjoint Set Union (Union-Find) Works

Imagine every node starts as its own boss (parent[i] = i):

• find(x): Follows parent pointers up to the root boss of x's group, and flattens the tree (parent[x] = find(parent[x]) — Path Compression) so future lookups are instant (O(1)).
• union(a, b): Finds the boss of a (pa) and the boss of b (pb). If pa == pb, they were already connected (meaning edge (a, b) creates an undirected cycle!). Otherwise, link parent[pa] = pb.

Quick Decision Table: Which Shortest-Path Algorithm Should You Pick?

3. Basic Operations & Walkthroughs (All 4 Languages)

import heapq

# 1. Dijkstra's Shortest Path from src -> O(E log V)
def dijkstra(n: int, adj: list[list[tuple[int, int]]], src: int) -> list[int]:
  dist = [float("inf")] * n
  dist[src] = 0
  pq = [(0, src)]  # (distance, node)
  while pq:
      d, u = heapq.heappop(pq)
      if d > dist[u]:
          continue  # Skip outdated heap entry
      for v, w in adj[u]:
          if d + w < dist[v]:
              dist[v] = d + w
              heapq.heappush(pq, (dist[v], v))
  return dist

# 2. Disjoint Set Union (Union-Find with Path Compression) -> O(alpha(N)) ≈ O(1)
class DSU:
  def __init__(self, n: int):
      self.parent = list(range(n))

  def find(self, x: int) -> int:
      if self.parent[x] != x:
          self.parent[x] = self.find(self.parent[x])
      return self.parent[x]

  def union(self, a: int, b: int) -> bool:
      pa, pb = self.find(a), self.find(b)
      if pa == pb:
          return False  # Already in same component (cycle!)
      self.parent[pa] = pb
      return True

4. Core Interview Patterns & Common Traps

# Union-Find Cycle & Component Counter:
components = n
for u, v in edges:
  if dsu.union(u, v):
      components -= 1   # Merged two separate islands!
  else:
      return [u, v]     # u and v were ALREADY connected -> redundant cycle edge!

5. Practice On Your Own (Curated Submodule Problems)