Dijkstra's Algorithm Analysis

1. Theoretical Foundation

The theoretical foundation of Dijkstra's algorithm (hereinafter referred to as the DJ algorithm) is a simple theorem:

The next shortest path is either the arc (V0, Vx) or a path that passes through some vertices in S and then reaches Vx. (S is the set of vertices with known shortest paths.)

(To describe the theorem accurately, I transcribed it directly. As for its correctness, well, it is said that it can be proved by contradiction.) Obviously, this is a recursive algorithm: repeatedly find the next one until there are no more.

2. Problem Analysis

Given a weighted directed graph as follows:

Find the shortest paths starting from V0 to all other vertices.

First, to convert it into a mathematical form that is easy to describe, we need to write the corresponding adjacency matrix (x represents unreachable):

0	50	10	x	45	x
x	0	15	x	10	x
20	x	0	15	x	x
x	20	x	0	35	x
x	x	x	30	0	x
x	x	x	3	x	0

Analyzing the theorem, we can conclude that currently there is only one vertex in set S: V0 (the path from V0 to itself is certainly the shortest). Besides the auxiliary space of set S, we also need:

• Set V: The set of vertices whose shortest paths are unknown, i.e., the complement of set S
• path[]: Records the shortest path to display the results
• dist[]: Records the path length, same as above
• Vx: Records the next vertex

The preparation is over, let's start solving.

3. Solving Process

0. Initial State

dist[] is initialized to the direct distance from V0 to each vertex (x represents not directly reachable). path[] is initialized to the corresponding path, and those not directly reachable are marked as NULL. Select vertex V2 with the minimum dist value in set V as the next vertex (Vx in the theorem).

1. Step 1

Add V2 to set S. We now have an additional transit point V2. Next, update dist[] to see if transiting through V2 is shorter. Update dist[] and path[] based on the calculation results, putting in the shorter path length and the corresponding path. Select V3 with the minimum dist value in set V as the next vertex.

2. Steps 2-5

Continue selecting the next vertex until there are no more selectable vertices in set V.

4. Summary

The process of the DJ algorithm is very simple:

1. Determine the first point in S (i.e., the source point V0);
2. Recurse according to the theorem (keep finding the shortest and try to use it as a transit point)

The logic of the algorithm itself is not difficult. The reason I didn't understand it before was that I got tangled up in specific pseudocode implementations. Therefore, when learning algorithms, one should focus on the logic rather than the specific implementation, especially with pseudocode algorithms that often randomly declare strange data structures without explaining why these auxiliary spaces are needed. For example, in this case, only one of set S or set V is needed, and path[] and dist[] could be clearly represented using a structure. However, the pseudocode used them all in a fragmented way, and the excessive auxiliary space actually hindered the understanding of the algorithm itself.