从某源点到其余各顶点的最短路径

　　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记录每一个顶点是否已经求得最短路径，在思想中即是判断顶点是属于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

　　Dist[index]=self.Arcs[Vertex][index]

　　flag[index]=0

　　if self.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

　　while index

　　MinDist=float(inf)

　　j=0

　　while j

　　if flag[j]==0 and Dist[j]

　　tVertex=j #tVertex为目前从V-S集合中找出的距离源点Vertex最断路径的顶点

　　MinDist=Dist[j]

　　j+=1

　　flag[tVertex]=1

　　EndVertex=0

　　MinDist=float(inf) #表示无穷大，若两点间的距离小于MinDist说明两点间有路径

　　#更新Dist列表，符合思想中第三条

　　while EndVertex

　　if flag[EndVertex]==0:

　　if self.Arcs[tVertex][EndVertex]

　　tVertex]+self.Arcs[tVertex][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: 无锡妇科医院哪家好 http://www.xasgfk.cn/

　　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

　　文章发布于: 2019-09-17 19:20:11