什么是Dijkstra算法？

Dijkstra算法是一种用于求解带权重图中最短路径的算法，由荷兰的计算机科学家Edsger W. Dijkstra在1959年提出。该算法适用于有向或无向图，但要求图中的边的权重必须为非负值。

该算法的基本思想是从起点开始，逐步确定到其他顶点的最短路径。在执行过程中，通过维护一个距离向量来记录到达各个顶点的最短路径长度，同时再维护一个集合来记录已经确定了最短路径的顶点。在每一次迭代中，选择距离向量中未确定最短路径的顶点中距离最小的顶点，更新距离向量和已确定最短路径的集合，并重复这个过程直到所有顶点都被确定了最短路径。

算法步骤

1. 初始化：设起点为源点，将源点到自己的距离设为0，将源点到其他顶点的距离初始化为无穷大。

distance[source] = 0
distance[others] = infinity

2. 选取距离向量中距离最小的顶点作为当前顶点。

min_distance = min(distance)
current_vertex = min_distance_vertex

3. 对于当前顶点的所有邻居顶点，计算经过当前顶点到达邻居顶点的距离，并更新距离向量。

for neighbour in neighbours(current_vertex):
    new_distance = distance[current_vertex] + weight(current_vertex, neighbour)
    if new_distance < distance[neighbour]:
        distance[neighbour] = new_distance

4. 标记当前顶点为已确定最短路径的顶点。

marked_vertices.add(current_vertex)

5. 重复步骤2到4，直到所有顶点都被标记为已确定最短路径的顶点。

算法示例

假设有以下带权重的无向图：

1 - 2 - 4

/ \ / \

0---3---5

起点为顶点0，我们使用Dijkstra算法来找到从起点到其他顶点的最短路径。

1. 初始化：

distance[0] = 0
distance[1-5] = infinity

2. 选取起点0作为当前顶点。

min_distance = 0
current_vertex = 0

3. 计算经过当前顶点到达其他顶点的距离，并更新距离向量：

distance[0-3] = [0, 6, 1, 2, infinity, infinity]

4. 将顶点0标记为已确定最短路径的顶点。

marked_vertices = {0}

5. 重复步骤2到4，依次选取经过顶点3和顶点1的最小距离顶点并更新距离向量，直到所有顶点都被标记为已确定最短路径的顶点。

最后得到的距离向量为：

distance = [0, 5, 1, 2, 6, 7]

可见，从顶点0到其他顶点的最短路径分别为：

0 - 2 - 4（距离为5）

0 - 3（距离为1）

0 - 3 - 5（距离为2）