5.3 Shortest paths and Dijkstra's algorithm

Motivation

A shortest-path problem asks for a route, not merely a way to connect the graph. Fix a source vertex s. For every reachable vertex v, the goal is to minimize the sum of the edge weights along an s-to-v path. This is the single-source shortest-path problem.

The central difficulty is that the first route discovered need not be the best one. A direct edge of weight 9 may later be replaced by a two-edge route of weights 3 and 2. Dijkstra's algorithm therefore keeps tentative prices, improves them by relaxation, and finalizes vertices only in a carefully chosen order.

Applicability condition — nonnegative weights only. Dijkstra's greedy finalization is correct only when every edge has weight at least zero. A zero-weight edge is allowed; a negative edge is not. A graph containing a negative edge requires a different shortest-path method.

This condition is part of the algorithm, not a technical footnote. Later we will give a three-vertex counterexample in which one negative edge makes the algorithm finalize the wrong distance.

Definitions

Let G=(V,E) be a directed or undirected graph, let w(u,v)\ge 0 be the weight of edge (u,v), and fix a source s. The weight of a path is the sum of its edge weights. Write delta(s,v) for the minimum path weight from s to v, and write infinity when v is unreachable.

Definition

Tentative distance and predecessor

d[v] is the smallest cost of an s-to-v path discovered so far. It is an upper bound on the true shortest distance delta(s,v). The value pred[v] records the vertex immediately before v on the path that currently realizes d[v].

Initially,

$$d[s]=0,\qquad d[v]=\infty\quad(v\ne s),$$

and every predecessor is undefined. Whenever a better path is found, the distance and predecessor must be changed together.

Definition

Relaxation

To relax an edge (u,v) of weight w(u,v), compare the old estimate d[v] with the candidate obtained by extending the current path to u:

$$\operatorname{candidate}=d[u]+w(u,v).$$

If the candidate is strictly smaller, set

$$d[v]\leftarrow d[u]+w(u,v),\qquad \operatorname{pred}[v]\leftarrow u.$$

Otherwise leave both fields unchanged.

The settled set S contains vertices whose shortest distances have been proved final. In each round, Dijkstra selects an unsettled vertex with minimum tentative distance, adds it to S, and relaxes its outgoing edges. A tie may be broken arbitrarily; it can change the predecessor tree but not the final distances.

Dijkstra(G, s):
  for each vertex v:
    d[v] = infinity
    pred[v] = undefined
  d[s] = 0
  S = empty set

  while an unsettled vertex has finite distance:
    u = unsettled vertex with minimum d[u]
    add u to S
    for each outgoing edge (u, v) with v not in S:
      candidate = d[u] + w(u, v)
      if candidate is smaller than d[v]:
        d[v] = candidate
        pred[v] = u

When the loop ends, a reachable target's path is reconstructed backwards: start at the target, follow pred until s, then reverse the sequence. A vertex left at infinity has no predecessor path from s.

Theorem/Proposition

Theorem

Finite estimates are path costs and upper bounds

At every point in Dijkstra's algorithm, each finite d[v] is the cost of an actual discovered path from s to v. Consequently,

$$d[v]\ge \delta(s,v).$$

Relaxation can only decrease an estimate, and it preserves this upper-bound property.

Theorem

Safe greedy finalization

Suppose all edge weights are nonnegative. When Dijkstra selects an unsettled vertex u having minimum tentative distance, its estimate is exact:

$$d[u]=\delta(s,u).$$

Thus u may be settled permanently.

Theorem

Predecessors encode shortest paths

After Dijkstra terminates, following predecessor links from any reachable vertex v back to s gives a path of cost d[v]. Since settled estimates are exact, that path is a shortest path. If several shortest paths tie, the stored predecessor records one of them.

Proof sketch or proof idea

The upper-bound claim follows by induction. The initialization d[s]=0 represents the empty path. Every later finite estimate is created by taking a path already represented by d[u] and appending edge (u,v). No estimate can therefore describe a cost smaller than the best possible path.

For the greedy step, assume the settled vertices already have exact distances, and let u be the unsettled vertex with minimum d. Consider a shortest path from s to u. Let y be the first unsettled vertex on that path and x its settled predecessor. When x was settled, (x,y) was relaxed, so d[y] became at most the cost of the shortest-path prefix ending at y. Combined with the upper-bound property, this gives

$$d[y]=\delta(s,y).$$

Every edge on the remaining suffix from y to u has nonnegative weight. Therefore delta(s,y)\le delta(s,u). Minimum selection and the upper-bound property now squeeze d[u] from both sides:

$$\delta(s,u)\le d[u]\le d[y] =\delta(s,y)\le\delta(s,u).$$

All quantities are equal, so d[u]=delta(s,u). The highlighted inequality can fail when a later edge is negative; that is exactly why the nonnegative-weight condition is indispensable.

Worked examples

Worked example

One relaxation changes both fields

Suppose d[u]=7, edge (u,v) has weight 4, and the current record is d[v]=14 with pred[v]=x. The route through u costs

$$7+4=11\lt14.$$

Relaxation sets d[v]=11 and pred[v]=u. If the old estimate had been 10, neither field would change. Updating only the number but not the predecessor would make later path reconstruction inconsistent with the recorded cost.

Worked example

Complete shortest-path trace from v0

Use the directed weighted graph with edges

v0->v1(3), v0->v2(2), v0->v3(6), v0->v4(4), v1->v3(5), v1->v5(5), v2->v4(1), v4->v3(2), v4->v5(4), and v3->v5(1).

In each distance cell below, the item in parentheses is the predecessor. A dash means undefined. After settling v2, both v1 and v4 have estimate 3; the trace breaks this tie by settling v1 first.

Stage	Chosen vertex	Settled set after the choice	d[v0]	d[v1]	d[v2]	d[v3]	d[v4]	d[v5]
Initial	—	{}	0 (—)	infinity (—)	infinity (—)	infinity (—)	infinity (—)	infinity (—)
Relax from v0	v0	{v0}	0 (—)	3 (v0)	2 (v0)	6 (v0)	4 (v0)	infinity (—)
Relax from v2	v2	{v0,v2}	0 (—)	3 (v0)	2 (v0)	6 (v0)	3 (v2)	infinity (—)
Relax from v1	v1	{v0,v2,v1}	0 (—)	3 (v0)	2 (v0)	6 (v0)	3 (v2)	8 (v1)
Relax from v4	v4	{v0,v2,v1,v4}	0 (—)	3 (v0)	2 (v0)	5 (v4)	3 (v2)	7 (v4)
Relax from v3	v3	{v0,v2,v1,v4,v3}	0 (—)	3 (v0)	2 (v0)	5 (v4)	3 (v2)	6 (v3)
Finish at v5	v5	{v0,v2,v1,v4,v3,v5}	0 (—)	3 (v0)	2 (v0)	5 (v4)	3 (v2)	6 (v3)

The final distances are 0,3,2,5,3,6. For example, the predecessor chain

$$v_5\leftarrow v_3\leftarrow v_4\leftarrow v_2\leftarrow v_0$$

reverses to the shortest path v0 -> v2 -> v4 -> v3 -> v5, whose cost is 2+1+2+1=6. Notice that v5 improved three times: infinity to 8, then 7, then 6. Discovery did not mean finalization.

Worked example

A minimal negative-edge failure

Consider the directed graph

s->u(1), s->v(2), and v->u(-2).

After relaxing edges out of s, Dijkstra has d[u]=1 and d[v]=2, so it settles u first. Yet the path s->v->u has cost 2+(-2)=0. When v is processed later, the algorithm would need to improve a vertex that it already declared final. The graph has no negative cycle; one negative edge alone is enough to invalidate greedy finalization.

Worked example

Weighted grid with an explicit node-to-edge convention

Find a minimum-cost route from the top-left cell to the bottom-right cell of this 3 by 4 node-weight grid, where N is blocked:

	Column 1	Column 2	Column 3	Column 4
Row 1	1	2	5	1
Row 2	4	1	N	N
Row 3	1	2	1	1

Create one vertex for each unblocked cell. Only a move one cell right or one cell down is allowed; omit an edge whose destination is outside the grid or blocked. Because the data put costs on nodes while Dijkstra expects costs on edges, choose and state this conversion:

$$w\bigl((i,j),(i',j')\bigr)=M[i'][j'], \qquad d[(1,1)]=M[1][1]=1.$$

Thus an edge charges the cost of entering its destination, while initialization charges the starting cell once. The shortest route to the bottom-right cell is

$$(1,1)\to(1,2)\to(2,2)\to(3,2)\to(3,3)\to(3,4),$$

with total node cost

$$1+2+1+2+1+1=8.$$

The competing route down the first column reaches (3,2) with cost 8, whereas the chosen route reaches it with cost 6; continuing along the common suffix would give totals 10 and 8. The top-row branch through (1,3) cannot descend because (2,3) and (2,4) are blocked. If instead one initialized the source to zero, the chosen edge sum would be 7; adding the source weight recovers the same reported node-path cost 8. Mixing those two conventions without saying so creates an off-by-one-cell error.

For an adjacency matrix and a linear scan for the next minimum, Dijkstra takes O(V^2) time. With adjacency lists and a min-priority queue implemented by a binary heap, there are at most V extract-min operations and at most E successful priority updates, giving

$$O((V+E)\log V)$$

time and O(V+E) graph-and-table space. In the right/down n by m grid, V\le nm and E\le 2nm-n-m; blocked cells only reduce those counts. The binary-heap bound is therefore O(nm log(nm)).

Implementation timing matters as much as the data structure. A vertex becomes settled when it is removed as the minimum, not when it is first inserted into the priority queue: insertion only records a tentative route that later relaxations may improve. If an implementation inserts a fresh queue entry instead of performing decrease-key, it must discard an extracted stale entry whose key no longer equals d[v]. Finally, if the smallest remaining key is infinity, every still-unsettled vertex is unreachable from s, so the algorithm may stop without inventing predecessor links.

Common mistakes

Common mistake

Using Dijkstra on a negative edge

Checking only for a negative cycle is not enough. Standard Dijkstra requires every edge weight to be nonnegative, even when the graph has no negative cycle.

Common mistake

Treating discovered as settled

A finite estimate means that one route is known. It does not become final until the vertex is extracted as the minimum unsettled vertex. The complete trace's three successive estimates for v5 make this distinction visible.

Common mistake

Updating distance without predecessor

Every strict improvement must update d[v] and pred[v] together. Otherwise the printed distance and reconstructed path may describe different routes.

Common mistake

Confusing shortest paths with BFS or an MST

BFS minimizes the number of edges when edges are unweighted or all have the same cost. Dijkstra minimizes total nonnegative weight. An MST minimizes the sum of edges needed to connect all vertices; it does not minimize each route from a chosen source.

Common mistake

Hiding a grid cost convention

If numbers belong to cells, say whether entering or leaving a cell pays that number and whether the source is counted. The route and its total are not auditable until that convention is fixed.

Summary

• d[v] is a tentative upper bound; pred[v] records the route realizing it.
• Relaxation tests whether extending the path through u improves v.
• The minimum unsettled estimate may be finalized because all remaining edge weights are nonnegative.
• Dijkstra supports zero-weight edges but not negative edges.
• Predecessors reconstruct a shortest path after distances are settled.
• BFS is the simpler shortest-path tool for unweighted graphs; Dijkstra handles nonnegative unequal weights; MST algorithms solve a different optimization problem.
• Complexity depends on representation: O(V^2) with matrix/linear selection, or O((V+E) log V) with adjacency lists and a binary heap.

Exercises

Checkpoint

What two fields change after a successful relaxation?

State both the numeric record and the path-reconstruction record.

1. Suppose d[a]=4, w(a,b)=6, d[b]=13, and pred[b]=x. Relax (a,b). Then repeat when d[b]=9.
2. Using the complete trace, reconstruct the shortest paths from v0 to v3 and v5, and verify both totals from the edge list.
3. Explain exactly which line of the safe-finalization proof fails in the graph s->u(1), s->v(2), v->u(-2).
4. A graph is unweighted and represented by adjacency lists. Which algorithm is the natural shortest-path choice, and what is its running time?
5. Under the weighted-grid convention above, what estimate is assigned to (3,2)? Compare the two routes to that cell discussed in the example.
6. State one difference among the objectives of BFS shortest paths, Dijkstra shortest paths, and a minimum spanning tree.

Solutions

Solution · Quick-check answer

A successful relaxation changes d[v] to the smaller candidate and changes pred[v] to the vertex through which that candidate was obtained.

Solution · Guided solutions

1. The candidate is 4+6=10. From 13, update to d[b]=10 and pred[b]=a. From 9, make no change because 10 is not smaller.
2. For v3, follow v3 ← v4 ← v2 ← v0, reverse it, and obtain v0->v2->v4->v3 with cost 2+1+2=5. For v5, append v3->v5(1), giving total 6.
3. The proof uses $\delta(s,y)\le\delta(s,u)$ because the suffix from y to u is assumed nonnegative. Here the suffix edge v->u has weight -2, so a vertex with the larger prefix estimate can later create the cheaper path.
4. Use BFS. Its queue explores increasing edge-count layers in O(V+E) time.
5. The estimate is 1+2+1+2=6 along (1,1)->(1,2)->(2,2)->(3,2). The other incoming route, (1,1)->(2,1)->(3,1)->(3,2), costs 1+4+1+2=8, so relaxation keeps 6.
6. BFS minimizes edge count in an unweighted graph. Dijkstra minimizes total nonnegative path weight from one source. An MST minimizes the total weight of a spanning tree connecting all vertices, without optimizing every source-to-target route.