新网创想网站建设,新征程启航

为企业提供网站建设、域名注册、服务器等服务

怎么在python中使用Dijkstra算法计算最短路径-创新互联

这篇文章将为大家详细讲解有关怎么在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

  • 则将源点到顶点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

输出结果如下:

请输入源点
a
请输入终点
f
从顶点a到顶点f的最短路径为:
['a', 'c', 'e', 'f']
最短路径长度为:17

关于怎么在python中使用Dijkstra算法计算最短路径就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。


网站题目:怎么在python中使用Dijkstra算法计算最短路径-创新互联
转载来源:http://wjwzjz.com/article/jihsj.html
在线咨询
服务热线
服务热线:028-86922220
TOP