Dijkstra, Prim, Kruskal and Topological Sort: Choosing the Right Graph Algorithm

Four algorithms, four different questions

Before any mechanics, fix what each one is for. Almost every wrong answer in this topic is an algorithm applied to the wrong question, not an algorithm executed badly.

Two consequences fall straight out of that table and are worth saying out loud.

First, Dijkstra and MST are not the same problem, even though both are greedy and both build a tree out of a weighted graph. A shortest-path tree minimises each individual distance from the source. A minimum spanning tree minimises the total weight of the whole tree. Those are different objectives and they generally produce different trees — you will see them differ by exactly one edge later on this page.

Second, Prim and Kruskal are the same problem. They are two strategies for one output. On a graph where all edge weights are distinct they return literally the same tree; where weights tie they may return different trees, but always with the same total weight.

Relaxation: the one idea Dijkstra is built from

Dijkstra keeps a single array, dist[], holding the best distance to each vertex known so far. Everything starts at infinity except the source, which is 0. These are guesses, and they only ever get smaller.

Relaxation is the act of improving one guess using one edge. Given an edge from u to v with weight w:

if (dist[u] + w < dist[v]) {
    dist[v] = dist[u] + w;   // found a cheaper way in, through u
    parent[v] = u;           // remember how we got here
}

That is the entire arithmetic content of the algorithm. Read it in English: if reaching u and then taking this edge is cheaper than whatever I currently believe about v, believe the cheaper thing instead. The name is mechanical — the estimate for v was stretched too tight, and the edge lets it relax down to a smaller value.

The loop around it is what makes the guesses final:

1. Among the vertices not yet settled, take the one with the smallest current dist.
2. Declare it settled. Its distance will never improve again.
3. Relax every edge leaving it.
4. Repeat until every vertex is settled.

Step 2 is the part that needs an argument, and the argument is the reason negative weights are banned. When you pick the smallest unsettled dist, any other route to that vertex would have to go through some other unsettled vertex first — one whose distance is already greater or equal — and then travel further along at least one more edge. With non-negative weights, travelling further can never make the total smaller, so no such route can win. Allow one negative edge and that sentence collapses: a longer prefix can be redeemed by a negative edge later, and a vertex you already froze turns out to have been wrong.

A useful mental separation while tracing by hand: settling a vertex is a decision you never revisit; relaxing an edge is a guess you may overwrite several times. In the trace below, vertex D is relaxed twice — 12 first, then 8 — before it is ever settled.

The graph everything on this page runs on

Seven vertices, A to G, ten undirected weighted edges:

A -- B (2)    A -- C (3)    B -- C (2)    B -- D (10)   C -- E (4)
D -- E (1)    D -- F (6)    E -- F (3)    E -- G (8)    F -- G (2)

As an adjacency list, which is how the code stores it:

Two features of this graph are deliberate. The edge B–D (10) is a trap: it is the only direct route into D from the left-hand side of the graph and it is expensive, so D is first relaxed to a bad value and later rescued from the other direction. And the triangle A–B (2), B–C (2), A–C (3) is what will make the shortest-path tree and the minimum spanning tree disagree.

Dijkstra traced from A, one settled vertex per row

Source A. Each row is one iteration: the vertex settled on the left with its final distance, and the state of the whole dist array after that vertex has relaxed all of its edges.

Walk the interesting rows.

• Settling B, not C. After A relaxes its two edges, B is at 2 and C is at 3, so B goes first. B then offers C a route of 2 + 2 = 4, which is worse than the 3 C already has, so nothing changes. This is the most commonly mis-traced moment on any Dijkstra paper: a relaxation that fails is still a step, and the failed comparison is exactly what you must write down to show your working.
• D relaxed to 12, then to 8. B is D's only neighbour early on, and B–D costs 10, so D sits at 12. Four rows later E is settled at 7 and the edge E–D (1) drops D to 8. A vertex's estimate improving after several rounds is normal; what would be a bug is an estimate improving after the vertex was settled.
• D is settled but changes nothing. When D's turn comes at 8, its edge to F offers 8 + 6 = 14, worse than F's existing 10. Some rows do no work. That is not a mistake in your trace.
• G relaxed twice. E gives G 15 via the expensive E–G (8); F later gives it 12. G is settled last, at 12.

Final answers, with the path reconstructed by walking the parent array backwards:

vertex  dist  path
  A     0  A
  B     2  A-B
  C     3  A-C
  D     8  A-C-E-D
  E     7  A-C-E
  F    10  A-C-E-F
  G    12  A-C-E-F-G

Note that the cheapest route to D does not use the only edge that touches D from the source's side of the graph in one hop. Greedy on the frontier, not greedy on the map.

Dijkstra in C++ with a priority queue

The program below is the source of the table above — it prints that table and then the path list, verbatim.

Two implementation points are worth more than the rest of the code.

Choosing the next vertex. The textbook version scans the whole dist array for the smallest unsettled entry, which is O(V) per round and O(V²) overall — perfectly fine for exam-sized graphs and easier to trace. The version here uses std::priority_queue with std::greater to turn the default max-heap into a min-heap, which gets you O((V + E) log V).

Stale heap entries. A priority queue has no decrease-key operation, so when a vertex is relaxed a second time you push a new pair rather than editing the old one. The old, worse pair is still sitting in the heap. The line if (done[u]) continue; is what discards it. Leave that line out and you will re-expand vertices, and on some graphs relax edges out of a vertex using a distance that is no longer current. In the trace above, D is pushed at 12 and again at 8; the 12 is popped later and thrown away.

INF is std::numeric_limits<int>::max(), so the guard dist[u] != INF before the addition matters: without it, INF + w overflows signed int, which is undefined behaviour, and in practice wraps to a large negative number that looks like a wonderfully short path.

#include <iostream>
#include <iomanip>
#include <limits>
#include <queue>
#include <string>
#include <vector>

const int INF = std::numeric_limits<int>::max();

struct Edge { int to; int w; };

// Undirected weighted graph, vertices 0..6 == A..G.
const std::string NAME = "ABCDEFG";

void addEdge(std::vector<std::vector<Edge>>& g, int u, int v, int w) {
    g[u].push_back({v, w});
    g[v].push_back({u, w});
}

void printRow(const std::string& label, const std::vector<int>& dist) {
    std::cout << std::left << std::setw(14) << label;
    for (std::size_t v = 0; v < dist.size(); ++v) {
        if (dist[v] == INF) std::cout << std::right << std::setw(4) << "inf";
        else                std::cout << std::right << std::setw(4) << dist[v];
    }
    std::cout << '\n';
}

int main() {
    const int V = 7;
    std::vector<std::vector<Edge>> g(V);
    addEdge(g, 0, 1, 2);   // A-B 2
    addEdge(g, 0, 2, 3);   // A-C 3
    addEdge(g, 1, 2, 2);   // B-C 2
    addEdge(g, 1, 3, 10);  // B-D 10
    addEdge(g, 2, 4, 4);   // C-E 4
    addEdge(g, 3, 4, 1);   // D-E 1
    addEdge(g, 3, 5, 6);   // D-F 6
    addEdge(g, 4, 5, 3);   // E-F 3
    addEdge(g, 4, 6, 8);   // E-G 8
    addEdge(g, 5, 6, 2);   // F-G 2

    const int src = 0;
    std::vector<int> dist(V, INF);
    std::vector<int> parent(V, -1);
    std::vector<bool> done(V, false);
    dist[src] = 0;

    // (distance, vertex); greater<> turns the max-heap into a min-heap.
    std::priority_queue<std::pair<int, int>,
                        std::vector<std::pair<int, int>>,
                        std::greater<std::pair<int, int>>> pq;
    pq.push({0, src});

    std::cout << std::left << std::setw(14) << "settled";
    for (int v = 0; v < V; ++v) std::cout << std::right << std::setw(4) << NAME[v];
    std::cout << '\n';
    printRow("(start)", dist);

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (done[u]) continue;   // stale heap entry: a better one was processed already
        done[u] = true;

        for (const Edge& e : g[u]) {
            if (dist[u] != INF && dist[u] + e.w < dist[e.to]) {
                dist[e.to] = dist[u] + e.w;   // relaxation
                parent[e.to] = u;
                pq.push({dist[e.to], e.to});
            }
        }
        printRow(std::string(1, NAME[u]) + " (" + std::to_string(d) + ")", dist);
    }

    std::cout << "\nvertex  dist  path\n";
    for (int v = 0; v < V; ++v) {
        std::string path(1, NAME[v]);
        for (int p = parent[v]; p != -1; p = parent[p]) path = NAME[p] + ("-" + path);
        std::cout << "  " << NAME[v] << std::right << std::setw(6) << dist[v]
                  << "  " << path << '\n';
    }
    return 0;
}

Minimum spanning trees: Kruskal merges a forest, Prim grows one tree

A spanning tree of a connected graph touches every vertex using the fewest edges that can do it: exactly V − 1, and no cycles. A minimum spanning tree is the spanning tree whose weights sum to the least. The V − 1 count is not a rule of thumb, it is a definition you can check your answer against — V − 2 edges cannot reach everything, V edges must contain a cycle. On our seven-vertex graph, any correct answer has six edges.

Kruskal ignores connectivity until the last moment. Sort all ten edges by weight, then walk the sorted list and take each edge unless its two endpoints are already connected to each other. Early on you are building several disconnected fragments — a forest — and the algorithm's job is to merge them. Cycle detection is done by union-find: find returns which fragment a vertex belongs to, unite merges two fragments and returns false if they were already the same one.

Kruskal (whole edge list, cheapest first)
  D-E (1)  take
  A-B (2)  take
  B-C (2)  take
  F-G (2)  take
  A-C (3)  skip: would close a cycle
  E-F (3)  take
  C-E (4)  take
  D-F (6)  skip: would close a cycle
  E-G (8)  skip: would close a cycle
  B-D (10)  skip: would close a cycle
  edges chosen: 6 (V-1 = 6), total weight 14

Read the order it accepted things: D–E, then A–B, then F–G. At that point Kruskal is holding three separate fragments that have nothing to do with each other. It is not building a tree, it is building a forest and merging it, and only the very last accepted edge (C–E) makes the thing connected.

Prim never has more than one fragment. Start at any vertex; repeatedly add the cheapest edge with one end inside the tree and one end outside; stop after V − 1 additions.

Prim (one tree, grown from A)
  add A-B (2)
  add B-C (2)
  add C-E (4)
  add E-D (1)
  add E-F (3)
  add F-G (2)
  total weight 14

Same six edges. Completely different order. Prim took C–E (4) as its third edge because at that moment 4 was the cheapest way out of the tree {A, B, C}; Kruskal took it last, after every cheaper edge in the graph had been considered. Prim added D–E (1) fourth; Kruskal added it first, before it knew anything about the rest of the graph. If a question asks for the order in which edges are chosen, the two algorithms give different — both correct — answers, and that is exactly what such a question is testing.

One more contrast that decides which one to implement: Kruskal needs the whole edge list up front and costs O(E log E) dominated by the sort, which suits sparse graphs. Prim only ever looks at the frontier and, in the simple array form below, costs O(V²) regardless of how many edges there are, which suits dense ones.

The program below produces both traces.

#include <algorithm>
#include <iostream>
#include <limits>
#include <string>
#include <vector>

const int INF = std::numeric_limits<int>::max();
const std::string NAME = "ABCDEFG";
const int V = 7;

struct Edge { int u; int v; int w; };

const std::vector<Edge> EDGES = {
    {0, 1, 2}, {0, 2, 3}, {1, 2, 2}, {1, 3, 10}, {2, 4, 4},
    {3, 4, 1}, {3, 5, 6}, {4, 5, 3}, {4, 6, 8}, {5, 6, 2},
};

// ---- union-find (disjoint set) -------------------------------------------
struct DSU {
    std::vector<int> parent, rank_;
    explicit DSU(int n) : parent(n), rank_(n, 0) {
        for (int i = 0; i < n; ++i) parent[i] = i;
    }
    int find(int x) {                       // path compression
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    bool unite(int a, int b) {              // false == already connected
        a = find(a); b = find(b);
        if (a == b) return false;
        if (rank_[a] < rank_[b]) std::swap(a, b);
        parent[b] = a;
        if (rank_[a] == rank_[b]) ++rank_[a];
        return true;
    }
};

void kruskal() {
    std::vector<Edge> es = EDGES;
    std::sort(es.begin(), es.end(),
              [](const Edge& a, const Edge& b) { return a.w < b.w; });

    DSU dsu(V);
    int total = 0, chosen = 0;
    std::cout << "Kruskal (whole edge list, cheapest first)\n";
    for (const Edge& e : es) {
        bool taken = dsu.unite(e.u, e.v);   // false: both ends already connected
        std::cout << "  " << NAME[e.u] << '-' << NAME[e.v] << " (" << e.w << ")  "
                  << (taken ? "take" : "skip: would close a cycle") << '\n';
        if (taken) { total += e.w; ++chosen; }
    }
    std::cout << "  edges chosen: " << chosen << " (V-1 = " << V - 1
              << "), total weight " << total << "\n\n";
}

void prim(int start) {
    std::vector<int> best(V, INF);   // cheapest edge joining v to the tree
    std::vector<int> from(V, -1);
    std::vector<bool> inTree(V, false);

    std::vector<std::vector<int>> w(V, std::vector<int>(V, INF));
    for (const Edge& e : EDGES) { w[e.u][e.v] = e.w; w[e.v][e.u] = e.w; }

    best[start] = 0;
    int total = 0;
    std::cout << "Prim (one tree, grown from " << NAME[start] << ")\n";
    for (int step = 0; step < V; ++step) {
        int u = -1;
        for (int v = 0; v < V; ++v)
            if (!inTree[v] && best[v] != INF && (u == -1 || best[v] < best[u])) u = v;
        if (u == -1) { std::cout << "  graph is disconnected\n"; return; }

        inTree[u] = true;
        if (from[u] != -1) {
            total += best[u];
            std::cout << "  add " << NAME[from[u]] << '-' << NAME[u]
                      << " (" << best[u] << ")\n";
        }
        for (int v = 0; v < V; ++v)
            if (!inTree[v] && w[u][v] < best[v]) { best[v] = w[u][v]; from[v] = u; }
    }
    std::cout << "  total weight " << total << '\n';
}

int main() {
    kruskal();
    prim(0);
    return 0;
}

Dijkstra versus Prim: the smallest total against the smallest edge

Both algorithms run the same outer loop — pick the cheapest thing on the frontier, absorb it, update the frontier — and the only difference is what cheapest measures.

That single missing dist[u] + is the whole difference, and it is the single most valuable line to have memorised on this topic.

Now watch it bite on our graph. Dijkstra from A produced this tree, reading the parent array: A–B (2), A–C (3), C–E (4), E–D (1), E–F (3), F–G (2) — total 15. The MST is A–B (2), B–C (2), C–E (4), D–E (1), E–F (3), F–G (2) — total 14.

They differ in exactly one edge. Both trees have to attach C somehow, and there are two candidates:

• Dijkstra keeps A–C (3). It is not comparing 3 against 2. It is comparing the route A–C (3) against the route A–B–C (2 + 2 = 4), and 3 wins. Keeping B–C would make C's distance from A equal to 4 — a worse answer to the question Dijkstra was asked.
• Prim and Kruskal keep B–C (2). They do not care how far C ends up from A. Once B is attached, joining C costs 2 this way and 3 the other way, so 2 wins, and the total drops from 15 to 14.

And the price the MST pays: in the minimum spanning tree, the only route from A to C is A–B–C, length 4, when the graph plainly contains a direct edge of length 3. A minimum spanning tree does not preserve shortest paths. If someone asks for the cheapest cabling to connect every building, that is fine. If they ask for the fastest route from the depot, it is the wrong tree.

A sanity check that costs five seconds and catches most confusion between the two: an MST answer is a set of edges with a total, and the set has exactly V − 1 members. A Dijkstra answer is a number per vertex. If your Dijkstra answer is a set of edges with a total, or your MST answer is a table of distances from a source, you have run the wrong algorithm.

Topological sort: order by in-degree, and get cycle detection for free

Different problem entirely. No weights, and the graph must be directed and acyclic (a DAG). An edge u → v means u must come before v. A topological order is any listing of the vertices that respects every such edge at once. Build systems, course prerequisites, spreadsheet recalculation and task schedulers all run on this.

The in-degree method — Kahn's algorithm — is the one to hand-trace, because its state is a single array of counters:

1. Compute the in-degree of every vertex: how many prerequisites it still has.
2. Put every vertex with in-degree 0 into a queue. These are the tasks that can start immediately.
3. Remove one from the queue, append it to the output, and decrement the in-degree of each of its successors. Any successor that drops to 0 has just had its last prerequisite satisfied — enqueue it.
4. Repeat until the queue is empty.

Take this dependency DAG on the same seven letters: A → C, B → C, C → D, C → E, D → F, E → F, B → G, G → E. Starting in-degrees are A 0, B 0, C 2, D 1, E 2, F 2, G 1, so the queue starts as [A, B].

A dash means the vertex has already been output. The result is A B C G D E F.

Three things to take from that trace.

The answer is not unique. A B C G D E F is one of twelve valid orderings of this DAG. Swap the queue for a stack and you get a different, equally correct one. Never write the topological order; write a topological order, and be ready to justify it edge by edge if a marker asks.

E waits for two different predecessors. It is reachable from C and from G, and it only becomes available on the fourth removal, when G finally clears its second dependency. The in-degree counter is doing exactly the bookkeeping you would otherwise do wrong in your head.

Cycle detection is free. If the loop ends with fewer than V vertices in the output, the leftovers are stuck in a cycle — each one is waiting on another one that is also waiting. Add F → C to this DAG and the program stops after emitting A, B and G: everything downstream is now waiting on itself. That check is one comparison and it is the only correct way to answer does a topological order exist.

Complexity is O(V + E): each vertex enters and leaves the queue once, and each edge is decremented once.

#include <iostream>
#include <queue>
#include <string>
#include <vector>

const std::string NAME = "ABCDEFG";
const int V = 7;

// Directed edges of a build-dependency DAG: u must come before v.
const std::vector<std::pair<int, int>> EDGES = {
    {0, 2}, {1, 2}, {2, 3}, {2, 4}, {3, 5}, {4, 5}, {1, 6}, {6, 4},
};

int main() {
    std::vector<std::vector<int>> succ(V);
    std::vector<int> indeg(V, 0);
    for (auto [u, v] : EDGES) { succ[u].push_back(v); ++indeg[v]; }

    std::queue<int> ready;
    for (int v = 0; v < V; ++v) if (indeg[v] == 0) ready.push(v);

    std::vector<int> order;
    std::cout << "removed  in-degrees after removal (A..G)\n";
    while (!ready.empty()) {
        int u = ready.front();
        ready.pop();
        order.push_back(u);
        for (int v : succ[u]) if (--indeg[v] == 0) ready.push(v);

        std::cout << "   " << NAME[u] << "     ";
        for (int v = 0; v < V; ++v) {
            bool out = false;
            for (int done : order) if (done == v) out = true;
            std::cout << (out ? " -" : " " + std::to_string(indeg[v]));
        }
        std::cout << '\n';
    }

    if (static_cast<int>(order.size()) != V) {
        std::cout << "\ncycle detected: only " << order.size() << " of " << V
                  << " vertices ever reached in-degree 0\n";
        return 0;
    }

    std::cout << "\ntopological order: ";
    for (int v : order) std::cout << NAME[v] << ' ';
    std::cout << '\n';
    return 0;
}

Three situations where Dijkstra is the wrong tool

The graph has no weights. Then BFS already solves it. On an unweighted graph every edge costs 1, so the number of edges on a path is its length, and BFS visits vertices in exactly non-decreasing order of that count — it settles the whole distance-1 layer, then the whole distance-2 layer, and so on. Running Dijkstra here is not wrong in the sense of giving a wrong answer; it gives the same answer while paying for a priority queue you did not need, turning O(V + E) into O((V + E) log V). If a question hands you an unweighted graph and asks for a shortest path, the expected answer is BFS, and reaching for Dijkstra suggests you have not noticed the weights are missing.

The converse trap is worse: running BFS on a weighted graph and reporting the fewest-hops path as the shortest. On the graph above, A–B–D is two hops and costs 12; A–C–E–D is three hops and costs 8. Fewest edges is not cheapest.

Some weight is negative. Dijkstra's freeze-the-smallest step assumes going further can never get cheaper, and a negative edge destroys that assumption. The failure is quiet — you get a number, it is just wrong. Bellman-Ford is the replacement: instead of settling one vertex per round it relaxes every edge, V − 1 times over, at O(V · E). It costs more and it buys two things: correctness with negative edges, and detection of a negative cycle (if a V-th pass still improves something, there is a loop you can go round forever getting cheaper, and shortest path stops being a meaningful question).

You need every pair, not one source. Running Dijkstra from all V sources works and is often the right practical choice on a sparse graph. On a dense one, Floyd-Warshall is simpler and competitive: three nested loops over dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]), O(V³), handling negative edges as long as there is no negative cycle. Its middle-out logic — k is allowed as an intermediate vertex now — is worth understanding once, because the three-line body is easy to reproduce from scratch and hard to reconstruct from a half-memory.

Complexity, and how to choose under time pressure

Two readings of that table that matter more than memorising the rows. Dijkstra and Prim appear twice each for the same reason: both repeatedly ask what is the smallest key still outstanding, and you either scan an array for it, O(V) per round, or keep a heap, O(log V) per push. So the dense choice is O(V²) and the sparse choice is the log one. And notice Kruskal's cost is dominated by the sort, not by the union-find, which is near-constant per operation in practice.

Matching the requirement to the algorithm, phrased the way questions phrase it:

One keyword heuristic that survives most phrasings: route, journey, from-here-to-there → shortest path. Connect everything, network, cable, total cost → spanning tree. Before, after, depends on, prerequisite → topological sort.

The mistakes people actually make

1. Running Prim's update rule inside a Dijkstra table. Writing w < dist[v] instead of dist[u] + w < dist[v]. The table fills in, every number looks plausible, and the answer is an MST-shaped object that answers nobody's question. If your Dijkstra distances are all small edge weights rather than growing totals, this is what happened.
2. Settling the vertex you just relaxed rather than the global minimum. Dijkstra settles the smallest key anywhere on the frontier, which is frequently not a neighbour of the vertex you just processed. On the graph above, after settling C at 3 the next vertex is E at 7 — not D, even though D was the thing most recently touched.
3. Not recording failed relaxations. 2 + 2 = 4, not less than 3, so C keeps 3. That comparison is a step of the algorithm and, in a hand trace, it is the evidence that you did the step.
4. Believing a distance can improve after settling. It cannot, with non-negative weights. If your trace shows a settled vertex changing, you either settled the wrong vertex or the graph has a negative edge and Dijkstra was never applicable.
5. Integer overflow on infinity. dist[u] + w where dist[u] is INT_MAX is undefined behaviour and typically wraps negative, producing spectacular fake shortcuts. Guard it, or use an INF like 1e9 that has headroom for one addition.
6. Forgetting the stale-entry check in the heap version. No decrease-key means duplicates in the queue. Without if (done[u]) continue; you re-expand vertices with out-of-date distances.
7. Producing an MST with the wrong number of edges. It is exactly V − 1. Fewer and it does not span; more and it has a cycle. Count before you write the total.
8. Doing Kruskal's cycle check by eye. On a small hand-drawn graph you can get away with it; in code, comparing whether two vertices are already connected is precisely what union-find is for, and a visited array does not do the same job — a fragment is not a vertex.
9. Assuming Prim and Kruskal must select edges in the same order. They select the same set (when weights are distinct) in almost always different sequences. Answer the question that was asked: set, total, or order.
10. Using Dijkstra's tree as a spanning tree, or an MST as a route map. Different objectives, demonstrated above: 15 against 14, and A-to-C is 3 in one tree and 4 in the other.
11. Topologically sorting an undirected graph. Meaningless — an undirected edge imposes no order — and any undirected edge is trivially a cycle, so no order exists. If the question says undirected, it is not asking for a topological sort.
12. Reporting a partial topological order as the answer. If the algorithm outputs fewer than V vertices, the correct answer is no topological order exists, the graph has a cycle, not the prefix it managed to emit.

Exercises with solutions

Work through each question before opening the solution below it.

Related pages