本文主要介绍pythonDijkstra算法实现最短路径问题的方法。文章通过示例代码介绍了最短路径问题的方法，对大家的学习或工作具有一定的参考学习价值。需要的朋友，跟着小编一起学习学习吧。 从一个源点到其他顶点的最短路径 Dijkstra算法可以用来求解图中一个源点到其他顶点的最短路径。假设G={V,{E}}是一个包含n个顶点的有向图。以图中的顶点v为源点，利用Dijkstra算法求顶点v到图中其他顶点的最短路径的基本思路如下： 用集合S记录最短路径的终点，初始S={v}。 选择长度最小的最短路径，这条路径的终点w属于V-S，将w并入S，记录最短路径的长度为Dw。 对于V-S中任意一个顶点为s，记录源点到顶点s的最短路径长度为Ds，记录顶点w到顶点s的弧的权重为Dws，若Dw+Dws 修改从源点到顶点s的最短路径长度为Dw+Ds=ws。 重复2和3，知道S=V。 为了实现算法， 使用邻接矩阵Arcs来存储有向网络。当i=j时，Arcs[i][j]=0；当i!=j时，如果下标i的顶点到达下标j的顶点有一条弧且该弧的权重为w，则Arcs[i][j]=w，否则Arcs[i][j]=float('inf')是无限的。 使用Dist存储从源到每个目的地的最短路径长度。 使用列表Path存储每条最短路径中倒数第二个顶点的下标。 用flag记录每个顶点是否获得了最短路径智汇返利http://www.kaifx.cn/broker/th...，以为是判断顶点是属于V集合还是属于V-S系列。 代码实现 #构建有向图Graph classGraph: def__init__(self,graph,labels):#labels为标点名称 self.Arcs=graph self.VertexNum=graph.shape[0] self.labels=labels defDijkstra(self,Vertex,EndNode):#Vertex为源点，EndNode为终点 Dist=[[]foriinrange(self.VertexNum)]#存储从源点到每个端点的最短路径长度 Path=[[]foriinrange(self.VertexNum)]#存储每个最短路径中倒数第二个顶点的下标 flag=[[]foriinrange(self.VertexNum)]#记录每个顶点是否获得最短路径 index=0 #初始化 whileindex Dist[index]=self.Arcs[Vertex][index] flag[index]=0 ifself.Arcs[Vertex][index] Path[index]=Vertex else: Path[index]=-1#表示没有从顶点Vertex到index的路径 index+=1 flag[Vertex]=1 Path[Vertex]=0 Dist[Vertex]=0 index=1 而index MinDist=float('inf') j=0 而j ifflag[j]==0andDist[j] tVertex=j#tVertex是当前从V-S集合中找到的源点Vertex的最短路径的顶点 flag[tVertex]=1 EndVertex=0 MinDist=float('inf')#代表无穷大，如果两点之间的距离小于MinDist，就说明有一个两点之间的路径 #更新DistList，符合第三项 而EndVertex ifflag[EndVertex]==0: ifself.Arcs[tVertex][EndVertex] tVertex]+self.Arcs[tVertex][EndVertex] Dist[EndVertex]=Dist[tVertex]+self.Arcs[tVertex][EndVertex] Path[EndVertex]=tVertex EndVertex+=1 指数+=1 vertex_endnode_path=[]#存储源点到终点的最短路径 returnDist[EndNode],start_end_Path(Path,Vertex,EndNode,vertex_endnode_path) #根据本文上面定义的Path，递归找到路径 defstart_end_Path(Path,start,endnode,path): ifstart==endnode: path.append(start) else: path.append(endnode) start_end_Path(Path,start,Path[endnode],path) returnpath if__name__=='__main__': #float('inf')表示无穷大 graph=np.array([[0,6,5,float('inf'),float('inf'),float('inf')], [float('inf'),0,2,8,float('inf'),float('inf')], [float('inf'),float('inf'),0,float('inf'),3,float('inf')], [float('inf'),float('inf'),7,0,float('inf'),9], [float('inf'),float('inf''),float('inf'),float('inf'),0,9], [float('inf'),float('inf'),float('inf'),float('inf'),0]]) G=Graph(graph,labels=['a','b','c','d','e','f']) start=input('请输入源点') endnode=input('请输入终点') dist,path=Dijkstra(G,G.labels.index(start),G.labels.index(endnode)) Path=[] foriinrange(len(path)): Path.append(G.labels[path[len(path)-1-i]]) print('从顶点{}到顶点{}的最短路径为：\n{}\n最短的长度path为：{}'.format(start,endnode,Path,dist)) 输出结果如下：到顶点f的最短路径为： ['a','c','e','f'] 最短路径长度为：17
