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