Graph Traversals, Minimum Spanning Trees and Shortest Paths
Three families of algorithm, and the questions are mostly about which one is licensed on the graph in front of you. Traversals are the simplest: BFS and DFS both cost O(V + E) on an adjacency list, and the difference that matters is what they compute. BFS explores by distance, so on an unweighted graph it gives shortest paths for free; DFS explores by depth, which is what makes it the basis of cycle detection, topological sorting and strongly connected components. Neither gives shortest paths on a weighted graph, and reaching for BFS there is a standard error. Minimum spanning trees come next, with two greedy algorithms that are both correct — Kruskal by sorted edge weight, Prim by growing one tree — and one fact worth stating precisely: the MST weight is always unique, the MST itself need not be. A graph whose edges all have distinct weights has exactly one MST; one with ties may have several, all of the same total. Shortest paths are where the licensing question bites hardest. Dijkstra is O(E log V) and wrong on negative edges — not slow, wrong — because it finalises a vertex the moment it is popped and a later negative edge can undercut that decision. Bellman–Ford is O(VE) and handles negative edges, and detects a negative cycle rather than looping forever. Floyd–Warshall is O(V³) and gives all pairs in three nested loops. Choosing among them is the exam's favourite question in this section, and the answer is decided by two properties of the graph — whether any weight is negative, and whether you need one source or all of them.
Minimum Spanning Trees: Unique Weight, Plural Trees
Take a graph on A, B, C, D with A–B, B–C and A–C all of weight 1, and C–D of weight 2. Kruskal takes two of the three unit edges — any two connect all of A, B, C — and then C–D, for a total weight of 4. But which two is a free choice, so there are three distinct minimum spanning trees, all weighing 4.
🎯 Why the weight is unique even when the tree is not
"Minimum" is a property of the number, so every minimum spanning tree has the same total by definition — if two spanning trees had different weights, the heavier one was not minimum. What is not forced is the choice among equal-weight edges, and that is the whole of the non-uniqueness. Two consequences are examinable. If all edge weights are distinct, the MST is unique — there is never a tie to break. And a question asking for "the minimum spanning tree" of a graph with repeated weights is ill-posed, while one asking for its weight is fine, so noticing ties tells you which kind of answer is being sought. The same reasoning applies to shortest paths: the distance is unique, the path need not be.| Aspect | Kruskal | Prim |
|---|---|---|
| Grows | A forest that merges | One tree from a start vertex |
| Needs | Sorted edges + union–find | A priority queue of vertices |
| Cost | O(E log E) | O(E log V) with a binary heap |
| Better on | Sparse graphs | Dense graphs |
Shortest Paths, and What Each Algorithm Is Allowed to Assume
| Algorithm | Cost | Handles negative edges? | Sources |
|---|---|---|---|
| BFS | O(V + E) | Unweighted only | One |
| Dijkstra | O(E log V) | No — gives wrong answers | One |
| Bellman–Ford | O(VE) | Yes, and detects negative cycles | One |
| Floyd–Warshall | O(V³) | Yes (no negative cycles) | All pairs |
⚠️ Dijkstra on a negative edge is wrong, not slow — here is the graph
Three vertices. A→B costs 1, A→C costs 2, C→B costs −2. Dijkstra from A pops B first, at distance 1, and finalises it — that is the algorithm's central assumption, that the smallest tentative distance can never be improved later. But the true shortest path to B is A→C→B, at 2 + (−2) = 0. Dijkstra reports 1. The failure is not a slow answer or an infinite loop; it is a confidently wrong number, which is why "use Dijkstra and add a large constant to every weight" does not fix it either — adding a constant per edge penalises paths with more edges and changes which path is shortest. Negative edges require Bellman–Ford, and that is the whole of the licensing question.The remaining choice is between one source and all. Bellman–Ford run from every vertex costs O(V²E), which on a dense graph where E ≈ V² is O(V⁴) — worse than Floyd–Warshall's O(V³), three nested loops over an adjacency matrix. On a sparse graph the comparison reverses. So even the all-pairs question comes back to density, exactly as the representation choice did.
Key takeaways
- BFS and DFS both cost O(V + E); BFS gives shortest paths only on an unweighted graph.
- DFS is the basis of cycle detection, topological sorting and strongly connected components.
- The MST weight is always unique; the MST is unique exactly when all edge weights are distinct.
- Kruskal is O(E log E) with union–find; Prim is O(E log V) with a binary heap.
- Dijkstra is WRONG on negative edges, not slow — it finalises a vertex the moment it is popped.
- Adding a constant to every weight does not fix that: it penalises paths with more edges.
- Bellman–Ford is O(VE), handles negative edges, and detects negative cycles.
- Floyd–Warshall gives all pairs in O(V³) — better than V runs of Bellman–Ford on a dense graph.
Practice questions (8)
Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.
A directed graph has edges A→B of weight 1, A→C of weight 2 and C→B of weight −2. Dijkstra from A reports the distance to B as:
Show answer
Answer: B — 1, which is wrong — the true distance is 0
Dijkstra pops the closest tentative vertex and finalises it. From A, B is tentatively 1 and C is 2, so B is popped first and fixed at 1 — before the edge C→B is ever examined. The true shortest path is A→C→B at 2 + (−2) = 0. So Dijkstra returns a confidently wrong number, which is the important part: it does not hang (option C) and it does not detect the problem. That is why negative edges require Bellman–Ford, and why the standard "fix" of adding a constant to every weight fails too — a constant per edge penalises longer paths and can change which path is shortest.A weighted graph has some edges of equal weight. Which statement is correct?
Show answer
Answer: B — The MST may be non-unique but its weight is unique
"Minimum" is a property of the number, so every minimum spanning tree has the same total by definition — a spanning tree of larger weight simply is not minimum. What ties leave free is which of several equal edges to take, and that is what makes the tree plural. A triangle of three unit edges plus one edge of weight 2 has weight 4 and three distinct MSTs. The corollary worth carrying: all-distinct weights force a unique MST. And this is why a question asking for "the MST" of a graph with ties is ill-posed while one asking for its weight is fine — the same distinction holds for shortest paths, where the distance is unique and the path need not be.To find shortest paths from one source in a weighted graph with no negative edges, the best choice is:
Show answer
Answer: B — Dijkstra, at O(E log V)
Dijkstra. BFS is cheaper but only correct when every edge costs the same, so it is not applicable to a weighted graph. Bellman–Ford is correct here but pays O(VE) for a generality — negative edges — that this graph does not need. Floyd–Warshall solves a bigger problem than was asked, all pairs rather than one source, and costs O(V³) for it. The habit worth building is to read the two properties off the question first: are any weights negative, and do I need one source or all? Those two answers pick the algorithm before any complexity is compared.Which of the following are true of BFS and DFS? (More than one may be correct.)
Show answer
Answer: A — Both run in O(V + E) on an adjacency list; B — BFS finds shortest paths in an unweighted graph; C — DFS is the basis of topological sorting
A, B and C. Both traversals touch every vertex once and every edge once, hence O(V + E) (A). BFS explores in order of hop count, which is the shortest path precisely when all edges cost the same (B). DFS's finishing order reversed is a topological order, which is why it underlies that algorithm as well as cycle detection and strongly connected components (C). D is false and is the point of the question — put unequal weights on the edges and a two-hop cheap path beats a one-hop expensive one, which BFS will already have finalised. Dijkstra is the repair, and it is essentially BFS with a priority queue.A graph on four vertices has edges A–B, B–C and A–C each of weight 1, and C–D of weight 2. What is the weight of its minimum spanning tree?
Numerical answer — type the value.
Show answer
Answer: 4
A spanning tree on four vertices has exactly three edges. Two of the three unit edges connect A, B and C — any two will do — and C–D is the only way to reach D, so the total is 1 + 1 + 2 = 4. Note what the question carefully asks for: the weight, which is unique. Asking for "the" tree would have been ill-posed, since the free choice among the three equal edges gives three distinct minimum spanning trees, all of weight 4. Answering 5 usually means taking all three unit edges, which would be a cycle and therefore not a tree.On a dense graph with E ≈ V², computing all-pairs shortest paths is cheapest with:
Show answer
Answer: B — Floyd–Warshall
Floyd–Warshall is O(V³) — three nested loops over the matrix. Bellman–Ford from every vertex is O(V·VE) = O(V²E), and with E ≈ V² that is O(V⁴), a whole factor of V worse. Option C is only valid for unweighted graphs. Option D solves a different problem entirely — a minimum spanning tree is not a shortest-path structure, and the path between two vertices in an MST need not be a shortest path, which is worth knowing as a fact in its own right. Note that on a sparse graph the comparison reverses, so density decides here just as it decided the representation choice.Bellman–Ford is preferred over Dijkstra when:
Show answer
Answer: B — Some edge weights are negative
Negative edge weights, and that is the only reason worth paying O(VE) for — Dijkstra is asymptotically faster and would be the choice otherwise. Bellman–Ford relaxes every edge V − 1 times rather than committing to a vertex when it is popped, so a later negative edge can still improve a distance; and a further relaxation that still improves something proves a negative cycle, which it reports rather than looping. Option A points the wrong way, since a larger graph favours the faster algorithm. Option C is Floyd–Warshall's job.If every edge weight in a connected graph is distinct, then:
Show answer
Answer: A — The minimum spanning tree is unique
Unique. Non-uniqueness comes entirely from ties: when two edges weigh the same, either may be taken and two different trees result. Remove every tie and each greedy step has exactly one best move, so Kruskal and Prim not only agree on the weight — which they always do — but return the same tree. Option C is impossible under any circumstances, since both algorithms are correct and every MST has the same total by definition. Option D confuses a property of the weights with a property of the structure: a graph with distinct weights can have as many cycles as it likes.