每对顶点之间的最短路径 试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态？

试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态？

1c:2

2c:2f:6

3c:2f:6e:10

4c:2f:6e:10d:11

5c:2f:6e:10d:11g:14

6c:2f:6e:10d:11g:14b:15

初始化d[i]是无限的。因为它从V4开始，所以D4=0并且选择了标记V4。

接下来，我们开始Dijkstra算法：

连接到V4的未标记点是V2和V6。这样，我们更新D2=20，D6=15，选择所有未标记点中最小的点，D6=15，并且选择了标记V6。这样，我们计算V4->V6的最短距离，D6=15；

从V6开始，连接到V6的未标记点是V2，然后计算D6=21>20，所以不更新D2，选择所有未标记点中最小的D2=20，标记V2已被选中，所以V4->v2的最短距离，D2=20；

从V2开始，V1和V5与V2连接且未标记，D1=D2，10=30，D5=D2 30=50，选择所有未标记点中的最小点，D1=30，标记V1已选中，因此我们计算V4->v1的最短距离，D1=30；

从V1开始，V3与V1连接且未标记，D3=D1 15=45，在所有剩余未选点中选择最小的D3=45（D5=50），标记V3已被选中，因此我们计算V4->v3的最短距离，D3=45

从V3开始，没有路径输出，不更新距离，在所有剩余未选点中选择最小的D5=50，标记V5已被选中，所以我们计算最短距离V4->v5，D5=50。

此时，所有点都被访问，结束。

注意：已选择上述标记点。注意：在算法的实现中，所有的点都被放入队列中。一旦选择了一个点，即计算了最短距离，该点将从队列中删除，直到队列为空。我写这个标记只是为了便于理解。

希望能帮助您清楚地了解图论中最重要的算法之一Dijkstra算法。

每对顶点之间的最短路径 用dijkstra算法求某一顶点 如果从无向图的任一顶点出发

版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。