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

来源：https://blog.csdn.net/qq_38233659/article/details/100936473