python如何实现Dijkstra算法–最短路径问题

本文借鉴于张广河教授主编的《数据结构》,对其中的代码进行了完善。 从某源点到其余各顶点的最短路径 D

本文借鉴于张广河教授主编的《数据结构》,对其中的代码进行了完善。

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

Dijkstra算法可用于求解图中某源点到其余各顶点的最短路径。假设G={V,{E}}是含有n个顶点的有向图,以该图中顶点v为源点,使用Dijkstra算法求顶点v到图中其余各顶点的最短路径的基本思想如下:

1.使用集合S记录已求得最短路径的终点,初始时S={v}。

2.选择一条长度最小的最短路径,该路径的终点w属于V-S,将w并入S,并将该最短路径的长度记为Dw。

3.对于V-S中任一顶点是s,将源点到顶点s的最短路径长度记为Ds,并将顶点w到顶点s的弧的权值记为Dws,若Dw+Dws

则将源点到顶点s的最短路径长度修改为Dw+Ds=ws。

4.重复执行2和3,知道S=V。

为了实现算法.

5.使用邻接矩阵Arcs存储有向网,当i=j时,Arcs[i][j]=0; 当i!=j时,若下标为i的顶点到下标为j的顶点有弧且弧的权值为w,则Arcs[i][j]=w,否则Arcs[i][j]=float(‘inf’)即无穷大。

6.使用Dist存储源点到每一个终点的最短路径长度。

7.使用列表Path存储每一条最短路径中倒数第二个顶点的下标。

8.使用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] 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

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] and Dist[

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:

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(从顶点{}到顶点{}的最短路径为:{}最短路径长度为:{}.format(start,endnode,Path,dist))

输出结果如下:

请输入源点

a

请输入终点

f

从顶点a到顶点f的最短路径为:

[a, c, e, f]

最短路径长度为:17

http://www.linuxprobe.com/chapter-00.html

    THE END
    喜欢就支持一下吧
    点赞7 分享
    评论 抢沙发
    头像
    欢迎您留下宝贵的见解!
    提交
    头像

    昵称

    取消
    昵称表情代码图片

      暂无评论内容