1
Fewest edges and least weight differ
A two-edge route of weight 20 loses to a five-edge route of weight 8. BFS answers the wrong question once weights exist.
Lesson · Graphs and Trees · Traversal
Shortest Paths and Dijkstra's Algorithm
With weights, breadth-first search no longer works. Dijkstra settles vertices in order of distance from the source, which is correct precisely because the weights are non-negative.
unweighted: BFS gives shortest paths
weighted: Dijkstra — settle the nearest unsettled vertex, relax its edges
requires NON-NEGATIVE weights
negative weights ⟹ Bellman–Ford instead
Weights change everything
Core ideas
What this lesson establishes
Two different questions — fewest edges and least total weight — and the second needs a different algorithm.
2
Dijkstra settles the nearest unsettled vertex
Once settled, a vertex's distance is final, because any other route would have to pass through a vertex already known to be further away.
3
Non-negativity is essential
A negative edge could make a longer detour cheaper, so a settled vertex might be improvable — and Dijkstra never revisits it.
The material
Weighted shortest paths
The algorithm, why it is correct, and where it fails.
Definition · Weighted graph and path weight
A weighted graph assigns each edge a number. The weight of a path is the sum of its edge weights, and a shortest path is one of minimum weight.
DIJKSTRA(G, s):
dist[s] = 0; dist[v] = ∞ for v ≠ s; all vertices unsettled
while some unsettled vertex has finite dist:
u = unsettled vertex with smallest dist
settle u
for each neighbour v of u:
if dist[u] + w(u,v) < dist[v]:
dist[v] = dist[u] + w(u,v); parent[v] = u
Theorem · Correctness
With non-negative weights, when Dijkstra settles a vertex u, dist[u] is the true shortest distance from s to u.
By induction on the order of settling. Suppose every previously settled vertex has its true distance, and consider the moment u is chosen.
Take any path P from s to u, and let x be its first vertex that is not yet settled, with predecessor y (settled). Then the length of P is at least dist[y] + w(y,x) ≥ dist[x] ≥ dist[u], the last step because u was chosen as the smallest.
The first inequality uses that the remaining part of P has non-negative weight — which is exactly where the hypothesis enters. So no path beats dist[u].
□
The proof names the place non-negativity is used, which is the useful way to read it: the argument is fine until a negative edge lets the tail of a path reduce its total.
Example · Where a negative edge breaks it
Vertices s, a, b with w(s,a) = 1, w(s,b) = 2, w(b,a) = −2. Dijkstra settles a at distance 1 and never reconsiders, but s → b → a has weight 0. The answer is wrong and the algorithm never notices.
Bellman–Ford handles negative weights by relaxing every edge n−1 times, at cost Θ(n|E|), and detects negative cycles — for which no shortest path exists at all, since going round the cycle again always reduces the total.
Cost
implementation of "smallest unsettled" cost
linear scan Θ(n² + |E|)
binary heap Θ((n + |E|) log n)
Fibonacci heap Θ(|E| + n log n)
For sparse graphs the heap version is much faster; for dense ones the simple scan is competitive. The choice is exactly “Graph Representations”'s representation trade-off appearing again.
With all weights equal to 1, Dijkstra settles vertices in the order BFS visits them, and the priority queue degenerates into a plain queue. BFS is Dijkstra's special case, which is why “Breadth-First and Depth-First Search” came first.
Interactive
Graph workbench
Your graph, the course's algorithms
Method
Running Dijkstra
Settle the nearest, relax its edges, repeat.
1
Initialise
Source at 0, everything else at infinity, nothing settled.
2
Settle the unsettled vertex with the smallest distance
Its distance is now final. This is the step the correctness proof justifies.
3
Relax its edges
For each neighbour, if going through the settled vertex is cheaper, update the distance and the parent.
4
Repeat until everything reachable is settled
Vertices still at infinity are unreachable. Follow the parent pointers backwards to recover a route.
Shortest paths
Score 0 / 0Choose the answer you can justify.
Cheapest and shortest disagree
s → a weight 10; s → b weight 3; b → a weight 2; a → t weight 1; b → t weight 9.
settle s dist: s=0, a=10, b=3, t=∞
settle b (3) relax: a = min(10, 3+2) = 5 t = min(∞, 3+9) = 12
settle a (5) relax: t = min(12, 5+1) = 6
settle t (6)
shortest by WEIGHT: s → b → a → t weight 6, three edges
shortest by EDGES: s → a → t (weight 11) or s → b → t (weight 12)
two edges each
BFS returns one of the two-edge routes: 11 or 12, against 6.
The relaxation of a from 10 down to 5 is the step BFS cannot perform: it settles a vertex on first contact and never improves it. That is exactly right when every edge costs 1 and wrong otherwise.
Common mistakes
1
Using BFS on a weighted graphIt answers "fewest edges", which is a different question and often a much more expensive route.
2
Applying Dijkstra with negative weightsIt returns a confident wrong answer. The failure is silent, which is the worst kind.
3
Adding a constant to make weights non-negativeIt penalises longer paths differently and changes the answer. It is a tempting fix and it does not work.
Check your understanding
✓
Finish when you can say where the correctness proof uses non-negativity.
Build a small graph with one negative edge and run Dijkstra by hand. Watch it settle a vertex whose distance later turns out to be improvable, and locate the step of the proof that fails.
Note: A* search is Dijkstra with a heuristic estimate added to each distance, guiding the search toward the target. It is correct when the heuristic never overestimates, and it is what route planners actually run.