Dijkstra's Algorithm
The cover image was generated by ChatGPT.
Introduction
Dijkstra’s Algorithm is a method for finding the shortest path between nodes in a graph. It was originally designed to find the shortest path between two points, but was later extended to find the shortest paths from a fixed point to all other points, forming what is called a “shortest path tree”.
How It Works
As shown above, suppose there are six locations labeled $A$, $B$, $C$, $D$, $E$, and $F$. We set $A$ as the starting point and $F$ as the destination, and we aim to find the shortest path from $A$ to $F$.
First, we calculate the distances between connected nodes, as shown below.
To find the shortest paths from $A$, we create a table to record the previous node and the current distance. Initially, all distances are set to infinity ($\infty$) to represent an unknown or infinite distance.
| Node | Marked | Distance | Previous Node |
|---|---|---|---|
| A | $\infty$ | ||
| B | $\infty$ | ||
| C | $\infty$ | ||
| D | $\infty$ | ||
| E | $\infty$ | ||
| F | $\infty$ |
Since we start at point $A$, the distance from $A$ to itself is 0.
| Node | Marked | Distance | Previous Node |
|---|---|---|---|
| A | 0 | ||
| B | $\infty$ | ||
| C | $\infty$ | ||
| D | $\infty$ | ||
| E | $\infty$ | ||
| F | $\infty$ |
Next, among all unmarked nodes, we select the one with the shortest distance and mark it as the optimal path.
| Node | Marked | Distance | Previous Node |
|---|---|---|---|
| A | ✓ | 0 | |
| B | $\infty$ | ||
| C | $\infty$ | ||
| D | $\infty$ | ||
| E | $\infty$ | ||
| F | $\infty$ |
After marking $A$, update its adjacent nodes. From the diagram, we see that $A$ is connected to $B$ and $C$, both with distances of 4, which are smaller than $\infty$, so we update them.
| Node | Marked | Distance | Previous Node |
|---|---|---|---|
| A | ✓ | 0 | |
| B | 4 | A | |
| C | 4 | A | |
| D | $\infty$ | ||
| E | $\infty$ | ||
| F | $\infty$ |
We again select the unmarked node with the shortest distance. Both $B$ and $C$ have a distance of 4. We mark $B$ first.
| Node | Marked | Distance | Previous Node |
|---|---|---|---|
| A | ✓ | 0 | |
| B | ✓ | 4 | A |
| C | 4 | A | |
| D | $\infty$ | ||
| E | $\infty$ | ||
| F | $\infty$ |
Now update $B$’s neighbors, $D$ and $E$. From $A$ through $B$ to $D$ is $4 + 7 = 11$, which is less than $\infty$, so we update $D$’s distance and set its previous node to $B$. Similarly, $A \rightarrow B \rightarrow E = 4 + 5 = 9$; we also update $E$.
| Node | Marked | Distance | Previous Node |
|---|---|---|---|
| A | ✓ | 0 | |
| B | ✓ | 4 | A |
| C | 4 | A | |
| D | 11 | B | |
| E | 9 | B | |
| F | $\infty$ |
Now we continue. Among the unmarked nodes, $C$ has the shortest distance. We mark it and attempt to update its neighbors $E$ and $F$.
| Node | Marked | Distance | Previous Node |
|---|---|---|---|
| A | ✓ | 0 | |
| B | ✓ | 4 | A |
| C | ✓ | 4 | A |
| D | 11 | B | |
| E | 9 | B | |
| F | $\infty$ |
The path from $C$ to $F$ is 16, so total distance is $4 + 16 = 20$, which is smaller than $\infty$, so we update $F$. As for $E$, the path via $C$ is 12, which is greater than the current distance of 9, so we don’t update.
| Node | Marked | Distance | Previous Node |
|---|---|---|---|
| A | ✓ | 0 | |
| B | ✓ | 4 | A |
| C | ✓ | 4 | A |
| D | 11 | B | |
| E | 9 | B | |
| F | 20 | C |
Repeat this process of marking and updating until all nodes are marked. The final table will look like this:
| Node | Marked | Distance | Previous Node |
|---|---|---|---|
| A | ✓ | 0 | |
| B | ✓ | 4 | A |
| C | ✓ | 4 | A |
| D | ✓ | 11 | B |
| E | ✓ | 9 | B |
| F | ✓ | 18 | E |
From this table, we can see that the shortest path from $A$ to $F$ is 18. We can backtrack from $F$ to $A$ to determine the shortest path: $$ A \Rightarrow B \Rightarrow E \Rightarrow F $$
Algorithm
Based on the above example, the general steps of Dijkstra’s Algorithm can be summarized as follows:
- Select the unmarked node with the smallest distance from the start.
- Mark that node as processed.
- For each neighboring node, calculate the total distance through the current node.
- If the total distance is less than the currently recorded distance, update the neighbor’s distance and record the current node as its previous node. If not, skip it.
- Repeat from step 1 until all nodes are marked.
Conclusion
When I first encountered this algorithm, I was amazed. It turns out that what we know as the “shortest path” can actually be computed with just a few simple steps. If I hadn’t seen this algorithm, I might have tried to brute-force every possible path!
References
戴克斯特拉演算法. (June 19, 2025). Wikipedia, the free encyclopedia. Retrieved July 2, 2025, from https://zh.wikipedia.org/zh-tw/戴克斯特拉算法
从0开始数. (January 29, 2021). 【算法】最短路径查找—Dijkstra算法 [Video]. YouTube. Retrieved July 2, 2025, from https://youtu.be/JLARzu7coEs
