好资源导航 » 文章资讯 » python Dijkstra算法实现最短路径问题的方法

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

2023-08-13 23:02:04 75

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

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

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
classGraph:
def__init__(self,graph,labels):#labels为标点名称
self.Arcs=graph
self.VertexNum=graph.shape[0]
self.labels=labels
defDijkstra(self,Vertex,EndNode):#Vertex为源点，EndNode为终点
Dist=[[]foriinrange(self.VertexNum)]#存储源点到每一个终点的最短路径的长度
Path=[[]foriinrange(self.VertexNum)]#存储每一条最短路径中倒数第二个顶点的下标
flag=[[]foriinrange(self.VertexNum)]#记录每一个顶点是否求得最短路径
index=0
#初始化
whileindex
输出结果如下：

请输入源点

a

请输入终点

f

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

['a','c','e','f']

最短路径长度为：17



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

返回顶部
514930285
czq8825@qq.com

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

热门推荐

随机推荐