Shortest paths, Dijkstra, Bellman-Ford, MSTs, DSU — a lot covered, a little left.
The graph section is almost done
Contents
Day 3 was the heaviest graph day yet. Shortest path algorithms, spanning trees, DSU, and a genuinely tricky implementation problem to open with. Three days in and graphs are almost wrapped. Not perfectly on schedule, but close enough that I’m not worried.
The hardest problem of the day
Alien Dictionary — topology + implementation
This one is dense. You compare adjacent words to extract ordering rules between characters, build a directed graph from those rules, then run Kahn’s algorithm to get the character order. The tricky edge case: if a longer word appears before a shorter one and the shorter is a prefix of the longer, the input is invalid — return empty string.
The implementation detail that gets you: use a set per adjacency node to avoid duplicate edges inflating indegrees. I wrote the full solution out and flagged it for daily re-reading. There’s a lot packed into it about sets, strings, and clean implementation.
Shortest path algorithms
Shortest path in a DAG — topo sort first
Run topo sort, get the stack. Initialize a distance array with infinity, source gets 0. Pop from the stack one by one and relax edges. Store weights in the adjacency list as pairs. Clean and efficient — works because DAGs have no cycles so the topo order guarantees you process nodes before their dependents.
Shortest path in undirected graph — BFS with relaxation
Unit weight edges, so BFS works. Instead of a visited array, track distances. Only push a neighbor if you’ve found a shorter path: if(dist[node]+1 < dist[n]). Simple but easy to forget you’re relaxing, not just visiting.
0-1 BFS — deque trick
When edge weights are only 0 or 1, skip Dijkstra entirely. Use a deque: push to front for weight 0, push to back for weight 1. This naturally keeps the deque sorted by cost. Think of it as a competitive programming optimization — special case Dijkstra with no priority queue overhead.
Dijkstra — min heap, relax neighbors
Same idea as the BFS version above, just with a priority queue instead. Push {dist, node}, always pop the minimum. Relax neighbors, push updated distances. Can also use an ordered set — the advantage is you can erase stale {dist, node} entries to skip unnecessary processing. Time: O(E log V).
Bellman-Ford — relax all edges N-1 times
The only algorithm here that handles negative weights. Relax every edge N-1 times — that’s the maximum number of edges in any shortest path without a cycle. Run it a Nth time: if any distance still updates, there’s a negative cycle. Slower at O(VE) but the only tool when weights go negative.
The bigger algorithms — theory locked in
Floyd-Warshall: All pairs shortest path. Three nested loops. O(n³) brute force but complete.
Prim’s: MST via priority queue. Pick smallest edge greedily, skip visited nodes. Sum is always unique.
DSU: Union-Find. Constant time component checks. Essential for dynamic graphs and Kruskal’s.
Kruskal’s: Sort edges ascending, pick smallest, use DSU to avoid cycles. Greedy MST.
SCC, Bridges, Articulation Points — flagged for tomorrow
These three are the remaining graph topics. SCC involves reversing edges and sorting by finish time before a final DFS. Bridges and articulation points are graph vulnerability problems. Couldn’t process these properly today — better to do them right than rush them tonight.
Tomorrow: Two Pointer playlist starts, and the last 3 graph topics get finished — one by one, properly.
