Graph Algorithms Part 2: Dijkstra and Topological Sort

A visual guide to finding shortest paths with Dijkstra's algorithm and ordering dependencies with Topological Sort. Includes step-by-step animations, code examples, and interactive visualizers.

Why These Algorithms Matter

This tutorial focuses on intuition and correctness. You will see exactly what data structures drive each algorithm and how each step changes the internal state.

Prerequisites and Assumptions

Before diving in, keep these constraints in mind:

• Dijkstra requires non-negative edge weights. If a graph contains a negative weight, Dijkstra is invalid.
• Topological Sort applies only to directed acyclic graphs (DAGs). If the graph contains a cycle, no topological ordering exists.

Part A: Dijkstra's Algorithm (Shortest Paths)

Dijkstra finds the shortest distance from a starting node to all other nodes in a weighted graph with non-negative weights. The core idea is greedy: repeatedly finalize the unvisited node with the smallest known distance, then relax its outgoing edges.

How It Works

1. Initialize distances: start node = 0, others = infinity
2. Use a priority queue keyed by current best distance
3. Repeatedly extract the node with the smallest distance
4. Relax each outgoing edge (try to improve neighbor distance)
5. Once a node is extracted (min chosen), its distance becomes final

Dijkstra Visual Walkthrough

Consider this example graph:

Nodes: A, B, C, D, E

Edges (directed with weights):

• A→B (4), A→C (2)
• C→B (1), C→D (8), C→E (10)
• B→D (5)
• D→E (2)

Step-by-step execution starting from A:

1. Start at A: dist(A)=0, dist(others)=∞
2. Pick A (0): Relax edges. dist(B)=4, dist(C)=2
3. Pick C (2): Relax edges. dist(B)=min(4, 2+1=3)→3, dist(D)=10, dist(E)=12
4. Pick B (3): Relax edges. dist(D)=min(10, 3+5=8)→8
5. Pick D (8): Relax edges. dist(E)=min(12, 8+2=10)→10
6. Pick E (10): No outgoing edges. Done.

Final distances: A=0, B=3, C=2, D=8, E=10

Dijkstra Common Pitfalls

• Wrong finalization timing: Marking nodes "visited" when pushed into the PQ is wrong. They become final only when extracted as minimum.
• Using a queue instead of a priority queue breaks correctness.
• Negative weights invalidate the greedy choice.

Part B: Topological Sort (Kahn's Algorithm)

Topological Sort produces a linear ordering of nodes such that for every directed edge U→V, U appears before V. This models dependencies: you cannot build V before U.

Kahn's algorithm repeatedly selects nodes with zero incoming edges, removes them, and updates the remaining in-degrees.

How It Works

1. Compute in-degree for every node
2. Add all nodes with in-degree 0 into a queue
3. Pop a node, append it to the ordering
4. "Remove" its outgoing edges by decrementing neighbors' in-degree
5. Any neighbor that becomes 0 is added to the queue
6. If ordering does not include all nodes, the graph contains a cycle

Topological Sort Example

Consider a dependency graph for a meal:

• Wash dishes → Cook
• Buy groceries → Cook
• Cook → Eat
• Eat → Clean up

One valid ordering: Buy groceries, Wash dishes, Cook, Eat, Clean up

Multiple valid orders can exist. Kahn's algorithm produces one based on tie-breaking rules.

Topological Sort Pitfalls

• Running topo on an undirected graph is invalid
• Cycles mean no valid ordering exists
• If you use DFS topo, you must handle recursion depth and visited states carefully (but this tutorial uses Kahn's algorithm)

Dijkstra vs Topological Sort

Code Examples

Dijkstra's Algorithm

#include <vector>
#include <queue>
#include <limits>

struct Edge {
  int to;
  int w;
};

std::vector<int> dijkstra(int start, const std::vector<std::vector<Edge>> & g) {
  const int INF = std::numeric_limits<int>::max();
  std::vector<int> dist(g.size(), INF);

  using P = std::pair<int,int>; // (dist, node)
  std::priority_queue<P, std::vector<P>, std::greater<P>> pq;

  dist[start] = 0;
  pq.push({0, start});

  while (!pq.empty()) {
    auto [d, v] = pq.top();
    pq.pop();

    if (d != dist[v]) { continue; }

    for (const auto & e : g[v]) {
      if (dist[v] != INF && dist[v] + e.w < dist[e.to]) {
        dist[e.to] = dist[v] + e.w;
        pq.push({dist[e.to], e.to});
      }
    }
  }
  return dist;
}

Topological Sort (Kahn's Algorithm)

#include <vector>
#include <queue>

std::vector<int> topoSort(const std::vector<std::vector<int>> & g) {
  int n = (int)g.size();
  std::vector<int> indeg(n, 0);

  for (int u = 0; u < n; u++) {
    for (int v : g[u]) {
      indeg[v]++;
    }
  }

  std::queue<int> q;
  for (int i = 0; i < n; i++) {
    if (indeg[i] == 0) { q.push(i); }
  }

  std::vector<int> order;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    order.push_back(u);

    for (int v : g[u]) {
      indeg[v]--;
      if (indeg[v] == 0) { q.push(v); }
    }
  }

  return order; // If order.size() < n, graph has a cycle
}

Common Pitfalls Summary

Summary

Dijkstra and Topological Sort solve two different but equally important problems: shortest paths and dependency ordering. Seeing their internal state step-by-step builds intuition that transfers directly to real systems like routing, scheduling, and build pipelines.

Try It Yourself

Use the interactive visualizer below to explore both algorithms. Switch between Dijkstra and Topological Sort modes, adjust graph parameters, and step through each micro-step to see exactly how the algorithms work.