千锋扣丁学堂Python培训之Dijkstra算法实现最短路径问题方法

2019-09-19 13:07:02 4641浏览

今天千锋扣丁学堂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

以上就是关于千锋扣丁学堂Python培训之Dijkstra算法实现最短路径问题方法全部内容,希望对大家的学习有所帮助,想要了解更多关于Python和人工智能方面内容的小伙伴,请关注扣丁学堂Python培训官网、微信等平台,扣丁学堂IT职业在线学习教育平台为您提供权威的Python开发环境搭建视频,Python培训后的前景无限,行业薪资和未来的发展会越来越好的,扣丁学堂老师精心推出的Python视频教程定能让你快速掌握Python从入门到精通开发实战技能。扣丁学堂Python技术交流群:279521237。


扣丁学堂微信公众号                          Python全栈开发爬虫人工智能机器学习数据分析免费公开课直播间


      【关注微信公众号获取更多学习资料】         【扫码进入Python全栈开发免费公开课】



查看更多关于"Python开发资讯"的相关文章>

标签: Python培训 Python视频教程 Python在线视频 Python学习视频 Python培训班
微信
微博
15311698296

全国免费咨询热线

邮箱:codingke@1000phone.com

官方群:148715490

北京千锋互联科技有限公司版权所有   北京市海淀区宝盛北里西区28号中关村智诚科创大厦4层
京ICP备2021002079号-2   Copyright © 2017 - 2022
返回顶部 返回顶部