Recap — Dijkstra and Topological Sort

# Dijkstra and Topological Sort Two named graph algorithms that interviewers expect you to know. Recognize the signals; reproduce the templates. ## Dijkstra's algorithm **Problem**: Shortest path from a source to all other nodes in a weighted graph with non-negative weights. ### The intuition Use a priority queue (min-heap). At each step, extract the unvisited node with smallest known distance; relax its edges (update neighbors' distances if going through this node is shorter). ### Template ```python import heapq from collections import defaultdict def dijkstra(graph, start): # graph: {u: [(v, weight), ...]} dist = {start: 0} pq = [(0, start)] # (distance, node) while pq: d, u = heapq.heappop(pq) if d > dist.get(u, float('inf')): # stale entry; skip continue for v, w in graph[u]: new_dist = d + w if new_dist < dist.get(v, float('inf')): dist[v] = new_dist heapq.heappush(pq, (new_dist, v)) return dist ``` Complexity: O((V + E) log V) with binary heap. ### When to use Dijkstra - Weighted graph, non-negative weights. - "Shortest path", "minimum cost path", "minimum time". - Network problems with edge costs. NOT for negative weights — use Bellman-Ford then. ### Common Dijkstra mistakes 1. **Negative weights.** Algorithm doesn't work; use Bellman-Ford. 2. **Forgetting the staleness check.** Without `if d > dist[u]: continue`, you reprocess and break correctness/efficiency. 3. **Storing nodes in PQ without distance.** Lose the priority. 4. **Doubling-counting visits.** Should NOT decrement priorities; push fresh entries and skip stale ones. ## Topological sort **Problem**: Order nodes of a DAG (Directed Acyclic Graph) such that for every edge u→v, u appears before v. ### Use cases - Course scheduling (prerequisites) - Build dependencies (compilation order) - Task scheduling ### Two approaches #### 1. DFS-based (post-order reverse) ```python def topo_sort_dfs(graph, n): visited = set() result = [] def dfs(u): if u in visited: return visited.add(u) for v in graph.get(u, []): dfs(v) result.append(u) # post-order for u in range(n): dfs(u) return result[::-1] # reverse for topo order ``` #### 2. Kahn's algorithm (BFS-based, in-degree) ```python from collections import defaultdict, deque def topo_sort_kahn(graph, n): in_degree = [0] * n for u in graph: for v in graph[u]: in_degree[v] += 1 q = deque(u for u in range(n) if in_degree[u] == 0) result = [] while q: u = q.popleft() result.append(u) for v in graph.get(u, []): in_degree[v] -= 1 if in_degree[v] == 0: q.append(v) if len(result) != n: return [] # cycle detected; topo sort impossible return result ``` Kahn's is often preferred — it also detects cycles cleanly. ### Cycle detection Topo sort fails if there's a cycle. Kahn's detects it: if `len(result) < n`, there's a cycle. DFS-based: track recursion stack; if you visit a node already in the current path, cycle. ```python def has_cycle(graph, n): WHITE, GRAY, BLACK = 0, 1, 2 color = [WHITE] * n def dfs(u): color[u] = GRAY for v in graph.get(u, []): if color[v] == GRAY: return True # back edge = cycle if color[v] == WHITE and dfs(v): return True color[u] = BLACK return False for u in range(n): if color[u] == WHITE and dfs(u): return True return False ``` The classic three-color DFS for cycle detection. ## When to use topo sort - "Course schedule" - "Build order" - "Find any valid sequence given dependencies" - "Detect if dependencies are circular" Signal: directed edges with "must do X before Y" semantics. ## The other named graph algorithms (briefly) Less common in interviews but worth recognizing: - **Bellman-Ford**: shortest path with negative weights. O(VE). - **Floyd-Warshall**: all-pairs shortest paths. O(V³). - **Prim's / Kruskal's**: minimum spanning tree. Build the cheapest tree connecting all nodes. - **Union-Find (Disjoint Set Union)**: connectivity queries, used in Kruskal's, common in graph problems. For most interview problems, BFS, DFS, Dijkstra, and topo sort cover everything. Know these four cold. ## Recognizing signals | Problem signal | Algorithm | |---|---| | "Shortest path, weighted, non-negative" | Dijkstra | | "Shortest path, negative weights" | Bellman-Ford | | "Course schedule / build order" | Topo sort | | "Detect cycle in directed graph" | DFS with recursion stack OR Kahn's | | "Minimum cost to connect all" | MST (Prim's/Kruskal's) | | "Connectivity queries / unions" | Union-Find | | "Shortest path, unweighted" | BFS | | "All reachable" | DFS | ## Common mistakes 1. **Dijkstra on negative edges.** Use B