Graph Algorithm Visualizations
Graph algorithms start with three different questions. Which dependency may run next? How cheaply can one source reach every vertex? How cheaply can the whole graph be connected? Topological sort answers the first, Dijkstra and Bellman-Ford the second, and minimum spanning trees the third.
The distinction matters. A shortest-path tree preserves the cheapest route from its source, even if the sum of all chosen edges is not globally minimal. A minimum spanning tree minimizes the network's total construction cost, even if the route between a particular pair becomes longer.
Compare the goals
| Algorithm | Goal | Next choice | Main safety condition | Typical time |
|---|---|---|---|---|
| Topological sort | order every dependency | zero-indegree source (Kahn) or vertex finishing on return (DFS) | graph is directed and acyclic | O(V + E) |
| Dijkstra | shortest distances from one source | unvisited vertex with smallest tentative distance | all edge weights are nonnegative | O((V + E) log V) |
| Bellman-Ford | shortest distances from one source | none — every edge, every pass | no negative cycle reachable from the source | O(V · E) |
| Prim | one minimum spanning tree | lightest edge crossing the current tree cut | graph is undirected and connected | O((V + E) log V) |
| Kruskal | one minimum spanning tree | next lightest edge joining two components | graph is undirected and connected | O(E log E) |
Dijkstra and Prim can both use a min-heap, but the heap contains different promises. Dijkstra orders tentative path distances from a source. Prim orders individual edges that cross out of one growing tree. Kruskal steps back from the source entirely: it sorts every edge and lets disjoint-set roots decide which connections are safe.
A recommended order
Start with Topological Sort after learning DFS and BFS. Kahn removes prerequisites from the front; DFS records vertices on the way back. The same DAG produces two different valid orders, while the Cycle preset makes both algorithms refuse a partial answer.
Then open Dijkstra. Follow the tentative-distance labels and watch relaxation improve a route that looked settled only a moment earlier. The important boundary is the Negative preset: once an edge can subtract cost, finalizing the smallest popped distance is no longer safe.
Then open Bellman-Ford on the Dijkstra's-trap preset — the exact graph Dijkstra just got wrong. No priority queue, no locking: every edge is relaxed V−1 passes in a row, so the negative edge is absorbed like any other, and one extra check sweep either certifies the answer or reports a negative cycle.
Then open Minimum Spanning Tree in Prim mode. The left ledger makes its cut visible, so each accepted edge has a local reason: it is the lightest current crossing. Notice that negative weights cause no trouble here.
Switch the same lesson to Kruskal without changing the graph. The geometry stays fixed while the proof changes. Now the bottom row is a globally sorted edge list, and the left ledger tracks connected components. When both endpoints have the same root, the highlighted accepted path explains exactly which cycle the candidate would close.
What to watch
- Ask what the priority value means. In Dijkstra it is a whole path cost; in Prim it is one edge weight.
- In topological sort, ask what still blocks a vertex. Kahn answers with a positive indegree; DFS answers with an unfinished outgoing dependency.
- Separate a greedy candidate from a safe candidate. A cheap edge is useful only when the algorithm's invariant allows it.
- Watch rejection beats. They expose the proof more clearly than routine acceptance: Dijkstra rejects stale queue entries, while MST algorithms reject cycle-closing edges.
- Try the disconnected graph. A partial forest is not a spanning tree, and a good implementation should say so.
All graph algorithm visualizations
Choose a lesson below, change its graph or algorithm, and step through the trace alongside the highlighted Python or JavaScript code.