Shortest Path Algorithms (Dijkstra's)

Dijkstra's algorithm finds the shortest path from a single source vertex to every other vertex in a weighted graph with non-negative edge weights. It is one of the most important algorithms in discrete mathematics and computer science.

---

The Problem

Given a weighted graph and a starting vertex $S$S, find the shortest (minimum weight) path from $S$S to every other vertex.

---

Dijkstra's Algorithm

Setup

Create a table with columns:

• Vertex: each vertex in the graph
• Permanent label: the confirmed shortest distance from $S$S
• Temporary label: the current best-known distance from $S$S (updated as the algorithm proceeds)
• Order of labelling: the order in which vertices receive permanent labels

Procedure

1. Give the starting vertex $S$S a permanent label of 0. All other vertices get temporary labels of $\infty$∞.
2. From the most recently permanently labelled vertex $V$V, update the temporary labels of all unlabelled neighbours:
   • New temporary label = $\min(\text{current temporary label}, \text{permanent label of } V + \text{edge weight})$min(current temporary label,permanent label of V+edge weight)
3. The unlabelled vertex with the smallest temporary label becomes permanently labelled.
4. Repeat from step 2 until all vertices are permanently labelled (or the target vertex is reached).

---

Worked Example

Consider a graph with vertices A, B, C, D, E and edges:

Edge	Weight
AB	4
AC	2
BC	1
BD	5
CD	8
CE	10
DE	2

Find the shortest path from A to all other vertices.

Step-by-Step Table

Order	Vertex	Permanent	From
1	A	0	—

Update from A: B = 4, C = 2.

Order	Vertex	Permanent	From
1	A	0	—
2	C	2	A

Update from C: B = min(4, 2+1) = 3, D = min(∞, 2+8) = 10, E = min(∞, 2+10) = 12.

Order	Vertex	Permanent	From
1	A	0	—
2	C	2	A
3	B	3	C

Update from B: D = min(10, 3+5) = 8.