Topological Sort (Kahn's) & Dijkstra's Shortest Path Algorithm
Master advanced graph algorithms. Implement Kahn's BFS Topological Sort for task scheduling, and Dijkstra's algorithm with PriorityQueue for weighted shortest paths.
By the end, you’ll be able to…
- Implement Topological Sorting on Directed Acyclic Graphs (DAGs) using Kahn's in-degree BFS algorithm.
- Implement Dijkstra's Algorithm using a Min-Heap PriorityQueue in O((V + E) log V) time.
- Understand why Dijkstra's algorithm fails when edges have negative weights.
01Topological Sort & Kahn's Algorithm
A Topological Sort of a Directed Acyclic Graph (DAG) is a linear ordering of its vertices such that for every directed edge u -> v, vertex u comes before vertex v in the ordering. This is the mathematical definition of Task Scheduling: you cannot take Advanced Java until you finish Intro to Programming.
Kahn's Algorithm solves topological sort using BFS and In-Degrees (the number of incoming edges to each node). 1) Compute in-degrees of all nodes. 2) Enqueue all nodes with in-degree 0 (no prerequisites). 3) Dequeue a node, add it to the topological order, and decrement the in-degree of its neighbors. If a neighbor's in-degree reaches 0, enqueue it. If the final order contains fewer than V nodes, a cycle exists!
02Dijkstra's Shortest Path Algorithm
In Weighted Graphs where edges have non-negative travel costs (such as road networks with distance or network routes with latency), standard BFS fails because fewest hops does not mean lowest total cost.
Dijkstra's Algorithm finds the shortest path from a starting vertex to all other vertices. It maintains a distance array dist initialized to infinity (dist[start] = 0) and a Min-Heap PriorityQueue storing (cost, vertex). At each step, it greedily pops the unvisited vertex with the smallest distance, and relaxes all its outgoing edges.
03The Negative Edge Trap
Dijkstra's algorithm relies on a Greedy Invariant: once a node is popped from the priority queue, its shortest distance is finalized and will never decrease. This assumption holds true ONLY when all edge weights are non-negative.
If an edge has a negative weight, a path through that negative edge could later reduce the distance of an already-finalized node, breaking Dijkstra's greedy assumption. For graphs with negative edge weights, we must use the Bellman-Ford algorithm or SPFA.
+---------------------------------------------------+| Dijkstra vs Bellman-Ford Complexity |+---------------------------------------------------+| Algorithm | Edge Weights | Time Complexity || Dijkstra | Non-negative (>=0)| O((V + E) log V)|| Bellman-Ford | Any (with cycle) | O(V * E) |+---------------------------------------------------+04Why This Matters in Production
Topological sort powers modern CI/CD build graph pipelines (GitHub Actions, Bazel, TurboRepo), executing independent tasks concurrently while respecting build order.
Dijkstra's algorithm powers GPS turn-by-turn navigation (Google Maps), internet packet routing (Open Shortest Path First / OSPF protocol), and cloud content delivery network (CDN) edge selection.
05Production Architecture & Engineering Trade-Offs
Graph algorithms power distributed network routing, dependency resolution, social graph analysis, and transaction fraud ring detection. In production enterprise graphs containing millions of vertices and billions of edges, naive adjacency matrix representations are completely impractical due to quadratic O(V^2) memory consumption.
Adjacency lists or compressed sparse row (CSR) formats are standard because they bound space consumption strictly to O(V + E). When implementing pathfinding algorithms like Dijkstra or A*, choosing the right priority queue implementation (such as 4-ary heaps or pairing heaps) and caching edge weights directly inside CPU cache lines delivers orders-of-magnitude faster convergence on real-world road and transit networks.
The ideas worth keeping.
- Kahn's in-degree BFS algorithm produces topological ordering and detects directed cycles in O(V + E) time.
- Dijkstra's algorithm finds single-source shortest paths on non-negative weighted graphs in O((V + E) log V) time.
- Never use Dijkstra on graphs with negative edges; use Bellman-Ford instead.
Make it yours.
Type and test your code right here in the interactive workspace. Run your solution, check the output, and compare with the worked guide when ready.
Exercise 1: Alien Dictionary Character Ordering
Explain how comparing adjacent words in a sorted dictionary builds a directed graph of character precedence solvable via Topological Sort.
Explore a worked solution
For adjacent words w1 and w2, find first differing char c1 and c2. Add directed edge c1 -> c2. Run Kahn's algorithm; the topological order yields the alien alphabet.Differing characters establish relative precedence, forming a DAG of character dependencies.
Exercise 2: Network Delay Time via Dijkstra
Given times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2, calculate the time for all nodes to receive a signal from node 2 using Dijkstra.
Explore a worked solution
Dijkstra yields dist: [node 1: 1, node 2: 0, node 3: 1, node 4: 2]. Maximum distance across all nodes is 2. Total time = 2.The maximum of the shortest distances represents the total time for the signal to reach all nodes.
What stayed with you?
Check the ideas while they’re fresh. Your answers stay in this page and feedback appears as you go.
Exercise 1: Alien Dictionary Character Ordering
Explain how comparing adjacent words in a sorted dictionary builds a directed graph of character precedence solvable via Topological Sort.
Build successful. (Java 15) [Process exited normally]
Keep exploring.
The official references behind this lesson, when you want a second angle or the full details.
One lesson closer.
Reading is a start. Trying it yourself makes the connection.