Python实现Dijkstra算法求解有向图最短路径

星野

发布时间：2026-10-13 | 3人浏览过

原创

本文基于《数据结构》理论，详细解析并完善使用Python实现Dijkstra算法求解有向图单源最短路径的方法。通过邻接矩阵存储图结构，利用数组记录距离、路径及访问状态，逐步扩展已知最短路径集合。文中提供完整代码示例及运行结果，展示如何从指定源点计算至终点的最短路径长度及具体节点序列。

Dijkstra算法原理与Python实现概述

本文内容参考张广河教授主编的《数据结构》，并对其中相关代码进行了优化与完善。

求解从指定源点到图中其余所有顶点的最短路径问题。

Dijkstra算法适用于计算有向图中某一源点到其余各顶点的最短路径。假设图G=（V，E）包含n个顶点，以顶点v为源点，利用Dijkstra算法求v到其余各顶点最短路径的基本思路如下：

引入集合S来记录已求得最短路径的终点，初始状态下S仅包含源点v，即S={v}。
选取一条长度最小的最短路径，该路径的终点w必须属于集合V-S。将w加入集合S，并将该最短路径的长度记为Dw。
对于集合V-S中的任意顶点s，设源点到顶点s的当前最短路径长度为Ds，并设顶点w到顶点s的弧的权值为Dws。若满足条件Dw+Dws<Ds，
则将源点到顶点s的最短路径长度更新为Dw+Dws（注：原文此处公式可能有误，逻辑应为Dw+Dws）。
重复执行上述步骤2和3，直到集合S包含所有顶点，即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。

Python代码实现与数据结构设计

以下是具体的代码实现部分。

核心算法逻辑与图类定义


#构造有向图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))