Dijkstra最短路径算法详细步骤

给定一个图和一个源点，图中散步不同位置的节点，Dijkstra算法就可以找到从源点到最短路径的节点。

Dijkstra的算法与Prim算法求最小生成树非常相似。算法生成以给定源点为根的最短路径树。需要维护两组数据，一组包含最短路径树中的节点，另一组包含尚未包含在最短路径树中的顶点。算法每进行一次，都会找到尚未包含的集合中的一个节点，并且与源点的距离最小。

以下是Dijkstra算法中用于查找从单个源点到给定图中所有其他节点的最短路径的详细步骤。

Dijkstra算法查找最短路径步骤

1)创建一个集合sptSet（最短路径树集），跟踪包含在最短路径树中的节点，即计算并确定其与源点的最小距离。

2)为输入图中的所有顶点分配一个距离值。将所有距离值初始化为INFINITE，将源点的距离值指定为0。

3）选择一个在sptSet中不存在且具有最小距离值的节点u。将u包含到sptSet中。

4)更新u到所有相邻节点的距离值。更新距离值，需要遍历所有相邻节点。对于每个相邻定义为v，如果u的距离值和uv的权重之和小于v的距离值，则更新v的距离值。

用Python实现Dijkstra最短路径算法

import sys
class Graph():
def __init__(self,vertices):
self.V=vertices
self.graph=[[0 for column in range(vertices)]
for row in range(vertices)]
def printSolution(self,dist):
print("Vertex\tDistance from Source")
for node in range(self.V):
print(node,"\t",dist[node])
def minDistance(self,dist,sptSet):
min=sys.maxsize
for u in range(self.V):
if dist<u>&lt;min and sptSet<u>==False:
min=dist<u>
min_index=u
return min_index
def dijkstra(self,src):
dist=[sys.maxsize]*self.V
dist[src]=0
sptSet=[False]*self.V
for cout in range(self.V):
x=self.minDistance(dist,sptSet)
sptSet[x]=True
for y in range(self.V):
if self.graph[x][y]&gt;0 and sptSet[y]==False and\
dist[y]&gt;dist[x]+self.graph[x][y]:
dist[y]=dist[x]+self.graph[x][y]
self.printSolution(dist)
g=Graph(9)
g.graph=[[0,4,0,0,0,0,0,8,0],
[4,0,8,0,0,0,0,11,0],
[0,8,0,7,0,4,0,0,2],
[0,0,7,0,9,14,0,0,0],
[0,0,0,9,0,10,0,0,0],
[0,0,4,14,10,0,2,0,0],
[0,0,0,0,0,2,0,1,6],
[8,11,0,0,0,0,1,0,7],
[0,0,2,0,0,0,6,7,0]
];
g.dijkstra(0);