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

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • python实现Dijkstra算法的最短路径问题

    迪杰斯特拉(Dijkstra)算法主要是针对没有负值的有向图,求解其中的单一起点到其他顶点的最短路径算法. 1 算法原理 迪杰斯特拉(Dijkstra)算法是一个按照路径长度递增的次序产生的最短路径算法.下图为带权值的有向图,作为程序中的实验数据. 其中,带权值的有向图采用邻接矩阵graph来进行存储,在计算中就是采用n*n的二维数组来进行存储,v0-v5表示数组的索引编号0-5,二维数组的值表示节点之间的权值,若两个节点不能通行,比如,v0->v1不能通行,那么graph[0,1]=+∞ (采

  • Python使用Dijkstra算法实现求解图中最短路径距离问题详解

    本文实例讲述了Python使用Dijkstra算法实现求解图中最短路径距离问题.分享给大家供大家参考,具体如下: 这里继续前面一篇<Python基于Floyd算法求解最短路径距离问题>的内容,这里要做的是Dijkstra算法,与Floyd算法类似,二者的用途均为求解最短路径距离,在图中有着广泛的应用,二者的原理都是老生常谈了,毕竟本科学习数据结构的同学是不可能不学习这两个算法的,所以在这里我也不再累赘,只简单概述一下这个算法的核心思想: Dijkstra算法的输入有两个参数,一个是原始的数据矩

  • Python数据结构与算法之图的最短路径(Dijkstra算法)完整实例

    本文实例讲述了Python数据结构与算法之图的最短路径(Dijkstra算法).分享给大家供大家参考,具体如下: # coding:utf-8 # Dijkstra算法--通过边实现松弛 # 指定一个点到其他各顶点的路径--单源最短路径 # 初始化图参数 G = {1:{1:0, 2:1, 3:12}, 2:{2:0, 3:9, 4:3}, 3:{3:0, 5:5}, 4:{3:4, 4:0, 5:13, 6:15}, 5:{5:0, 6:4}, 6:{6:0}} # 每次找到离源点最近的一个顶

  • python Dijkstra算法实现最短路径问题的方法

    本文借鉴于张广河教授主编的<数据结构>,对其中的代码进行了完善. 从某源点到其余各顶点的最短路径 Dijkstra算法可用于求解图中某源点到其余各顶点的最短路径.假设G={V,{E}}是含有n个顶点的有向图,以该图中顶点v为源点,使用Dijkstra算法求顶点v到图中其余各顶点的最短路径的基本思想如下: 使用集合S记录已求得最短路径的终点,初始时S={v}. 选择一条长度最小的最短路径,该路径的终点w属于V-S,将w并入S,并将该最短路径的长度记为Dw. 对于V-S中任一顶点是s,将源点到顶点

  • python标准算法实现数组全排列的方法

    本文实例讲述了python标准算法实现数组全排列的方法,代码来自国外网站.分享给大家供大家参考.具体分析如下: 从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列.当m=n时所有的排列情况叫全排列. def Mideng(li): if(type(li)!=list): return if(len(li)==1): return [li] result=[] for i in range(0,len(li[:])): bak=li[:] h

  • 详解Dijkstra算法之最短路径问题

    一.最短路径问题介绍 问题解释: 从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径,称为最短路径 解决问题的算法: 迪杰斯特拉算法(Dijkstra算法) 弗洛伊德算法(Floyd算法) SPFA算法 这篇博客,我们就对Dijkstra算法来做一个详细的介绍 二.Dijkstra算法介绍 2.1.算法特点 迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题,算法最终得到一个最短路径树.该算法常用于路由算法或者作为其他图算法的一个子模块. 2.2.算法的

  • JS使用Dijkstra算法求解最短路径

    一.Dijkstra算法的思路 Dijkstra算法是针对单源点求最短路径的算法. 其主要思路如下: 1. 将顶点分为两部分:已经知道当前最短路径的顶点集合Q和无法到达顶点集合R. 2. 定义一个距离数组(distance)记录源点到各顶点的距离,下标表示顶点,元素值为距离.源点(start)到自身的距离为0,源点无法到达的顶点的距离就是一个大数(比如Infinity). 3. 以距离数组中值为非Infinity的顶点V为中转跳点,假设V跳转至顶点W的距离加上顶点V至源点的距离还小于顶点W至源点

  • Java利用Dijkstra算法求解拓扑关系最短路径

    目录 算法简介 代码实现思路 算法思想 代码示例 算法简介 迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学迪家迪杰斯特拉于1959年提出的,因此又叫狄克斯特拉算法.是从一个顶点到其余各顶点最短路劲算法,解决的是有权图中最短路径问题.迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止. 代码实现思路 1.先初始化源节点(起始点)到其他各个拓扑节点的最短距离,可以用map存放,key为节点,value为节点到源节点的距

  • java实现最短路径算法之Dijkstra算法

    前言 Dijkstra算法是最短路径算法中为人熟知的一种,是单起点全路径算法.该算法被称为是"贪心算法"的成功典范.本文接下来将尝试以最通俗的语言来介绍这个伟大的算法,并赋予java实现代码. 一.知识准备: 1.表示图的数据结构 用于存储图的数据结构有多种,本算法中笔者使用的是邻接矩阵. 图的邻接矩阵存储方式是用两个数组来表示图.一个一维数组存储图中顶点信息,一个二维数组(邻接矩阵)存储图中的边或弧的信息. 设图G有n个顶点,则邻接矩阵是一个n*n的方阵,定义为: 从上面可以看出,无

  • C#图表算法之最短路径

    目录 1.最短路径的性质 最短路径 2.加权有向图的数据结构 加权有向图边的API 加权有向图的API 最短路径的API 最短路径的数据结构 边的松弛 顶点的松弛 3.最短路径算法的理论基础 最优性条件 验证 通用算法 4.Dijkstra 算法 数据结构 实现 变种 给定两点的最短路径. 任意顶点对之间的最短路径 欧几里得图中的最短路径 5.无环加权有向图中的最短路径算法 最长路径 并行调度任务 相对最后期限限制下的并行任务调度 向任务调度问题中添加的最后期限限制 6.一般加权有向图中的最短路

随机推荐