python Dijkstra算法实现最短路径问题的方法
本文借鉴于张广河教授主编的《数据结构》,对其中的代码进行了完善。
从某源点到其余各顶点的最短路径
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<Ds,
- 则将源点到顶点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记录每一个顶点是否已经求得最短路径,在思想中即是判断顶点是属于V集合,还是属于V-S集合。
代码实现
#构造有向图Graph class Graph: def __init__(self,graph,labels): #labels为标点名称 self.Arcs=graph self.VertexNum=graph.shape[0] self.labels=labels def Dijkstra(self,Vertex,EndNode): #Vertex为源点,EndNode为终点 Dist=[[] for i in range(self.VertexNum)] #存储源点到每一个终点的最短路径的长度 Path=[[] for i in range(self.VertexNum)] #存储每一条最短路径中倒数第二个顶点的下标 flag=[[] for i in range(self.VertexNum)] #记录每一个顶点是否求得最短路径 index=0 #初始化 while index<self.VertexNum: Dist[index]=self.Arcs[Vertex][index] flag[index]=0 if self.Arcs[Vertex][index]<float('inf'): #正无穷 Path[index]=Vertex else: Path[index]=-1 #表示从顶点Vertex到index无路径 index+=1 flag[Vertex]=1 Path[Vertex]=0 Dist[Vertex]=0 index=1 while index<self.VertexNum: MinDist=float('inf') j=0 while j<self.VertexNum: if flag[j]==0 and Dist[j]<MinDist: tVertex=j #tVertex为目前从V-S集合中找出的距离源点Vertex最断路径的顶点 MinDist=Dist[j] j+=1 flag[tVertex]=1 EndVertex=0 MinDist=float('inf') #表示无穷大,若两点间的距离小于MinDist说明两点间有路径 #更新Dist列表,符合思想中第三条 while EndVertex<self.VertexNum: if flag[EndVertex]==0: if self.Arcs[tVertex][EndVertex]<MinDist and Dist[ tVertex]+self.Arcs[tVertex][EndVertex]<Dist[EndVertex]: Dist[EndVertex]=Dist[tVertex]+self.Arcs[tVertex][EndVertex] Path[EndVertex]=tVertex EndVertex+=1 index+=1 vertex_endnode_path=[] #存储从源点到终点的最短路径 return Dist[EndNode],start_end_Path(Path,Vertex,EndNode,vertex_endnode_path) #根据本文上述定义的Path递归求路径 def start_end_Path(Path,start,endnode,path): if start==endnode: path.append(start) else: path.append(endnode) start_end_Path(Path,start,Path[endnode],path) return path 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=[] for i in range(len(path)): Path.append(G.labels[path[len(path)-1-i]]) print('从顶点{}到顶点{}的最短路径为:\n{}\n最短路径长度为:{}'.format(start,endnode,Path,dist))
输出结果如下:
请输入源点
a
请输入终点
f
从顶点a到顶点f的最短路径为:
['a', 'c', 'e', 'f']
最短路径长度为:17
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。
赞 (0)