4.4 Advanced Graph Algorithms

Deep Dive: Dijkstra Step by Step

Beginner tip: When graph edges have weights (like road distances), BFS no longer finds the shortest path. Dijkstra's algorithm does -- it always expands the closest unvisited node, like a GPS routing you through traffic. For interviews, master Dijkstra and topological sort. The rest (Bellman-Ford, Floyd-Warshall, Kruskal's) are good to know but rarely tested.

Network Delay Time

Graph: node 2 sends signal. Edges: 2->1 (1), 2->3 (1), 3->4 (1).

Start: dist = {2:0}, heap = [(0,2)]

Pop (0,2): visit node 2
  -> neighbor 1: 0+1=1, push (1,1). dist={2:0, 1:1}
  -> neighbor 3: 0+1=1, push (1,3). dist={2:0, 1:1, 3:1}

Pop (1,1): visit node 1. No outgoing edges.

Pop (1,3): visit node 3.
  -> neighbor 4: 1+1=2, push (2,4). dist={2:0, 1:1, 3:1, 4:2}

Pop (2,4): visit node 4. No outgoing edges.

All nodes visited. Max distance = 2. Answer: 2.

Topological Sort -- Alien Dictionary

Given sorted alien words: ["wrt", "wrf", "er", "ett", "rftt"]

Compare adjacent words to find edges:
  "wrt" vs "wrf": first diff at index 2: t->f
  "wrf" vs "er":  first diff at index 0: w->e
  "er"  vs "ett": first diff at index 1: r->t
  "ett" vs "rftt": first diff at index 0: e->r

Graph: t->f, w->e, r->t, e->r
Topo sort: w -> e -> r -> t -> f
Alien alphabet order: wertf

---

Before You Start -- How to Think About Advanced Graphs

When to Go Beyond BFS/DFS

BFS/DFS handle: unweighted shortest path, traversal, connectivity, cycle detection.

You need more when:
  - Edges have WEIGHTS -> Dijkstra
  - Need ALL-PAIRS shortest path -> Floyd-Warshall
  - Need DEPENDENCY ORDERING -> Topological Sort
  - Need to find BRIDGES / cut points -> Tarjan's
  - Need MINIMUM SPANNING TREE -> Kruskal's / Prim's

Dijkstra -- The One You Must Know

What: Shortest path from a source to all other nodes in a weighted graph (non-negative weights).
How: Greedy + min-heap. Always expand the closest unvisited node.
Complexity: O((V+E) log V)

Template:
  1. distances = {node: infinity for all nodes}, distances[start] = 0
  2. min-heap with (0, start)
  3. Pop smallest, update neighbors if shorter path found

Topological Sort -- For Dependencies

What: Order nodes so that for every edge A->B, A comes before B.
Only works on DAGs (directed acyclic graphs).

Kahn's Algorithm (BFS):
  1. Compute in-degree of every node
  2. Add all nodes with in-degree 0 to queue
  3. Process queue: remove node, decrement neighbors' in-degree
  4. If neighbor's in-degree becomes 0, add to queue
  5. If result length < total nodes -> cycle exists!

Interview Priority

Algorithm	Interview Frequency	Priority
Dijkstra	Medium-High	Must know
Topological Sort	Medium	Must know
Bellman-Ford	Rare	Know concept
Floyd-Warshall	Rare	Know concept
Kruskal's/Prim's	Rare	Know concept
Tarjan's	Rare	Bonus

Priority: Master Dijkstra and Topological Sort. Know the others exist.

Problems

#	Problem	Algorithm	Status
1	Network Delay Time	Dijkstra	[ ]
2	Cheapest Flights Within K Stops	Bellman-Ford	[ ]
3	Course Schedule II	Topological Sort	[ ]
4	Alien Dictionary	Topological Sort	[ ]
5	Min Cost to Connect All Points	Prim's/Kruskal's	[ ]
6	Swim in Rising Water	BS + BFS	[ ]
7	Critical Connections (Bridges)	Tarjan's	[ ]
8	Is Graph Bipartite?	BFS 2-coloring	[ ]

Priority: Dijkstra is commonly tested. Others are bonus/optional.

Notes