python Dijkstra算法实现最短路径问题的方法
作者:会飞的哼哧 发布时间:2022-02-21 03:08:51
标签: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
来源:https://blog.csdn.net/qq_38233659/article/details/100936473
0
投稿
猜你喜欢
- python除法负数商的取整方式与C++不同python:5 / -2 = -3若想和C++行为相同,可以使用 int(operator.t
- 从2003年到现在,从ACCESS到SQL SERVER的使用。在ACCESS中没有存储过程的概念。在使用过程中,发现ACCESS与SQL
- 将转储设备加入到SQL Server备份数据库的地方。在SEM中转储设备是可见性的,并且在设备上的信息被存储在主要数据库的sysdevice
- 前言前面一直使用命令行运行pytest用例,本篇来学下使用pytest.main()来运行测试用例pytest.main()args 传一个
- 匿名函数什么是匿名函数用一句话表达只有返回值的函数就是匿名函数。匿名函数只用来实现一些简单的函数功能,所以追求代码的简洁和高效。使用关键字
- //匹配中文 数字 字母 下划线 var checkIn
- 除了在Matlab中使用PRTools工具箱中的svm算法,Python中一样可以使用支持向量机做分类。因为Python中的sklearn库
- 场景分析一般Linux系统默认自带两个版本的python,我按照的虚拟机系统自带的版本为python2.7和python3.2,但是由于个人
- Event Handler在HDA中,要创建Python脚本,需要先选择一个事件处理器(EventHandle),他表示你要在什么时候执行你
- 1:php地址 http://127.0.0.6/?c=json2:java 输出的结果是[{"i
- Python 多进程默认不能共享全局变量主进程与子进程是并发执行的,进程之间默认是不能共享全局变量的(子进程不能改变主进程中全局变量的值)。
- 是建立一个数据集 前面应该先定义此数据集 dim rs as adodb.recordset 然后就可以用 set rs=server.Cr
- 脚本内容代码如下:from mitmproxy import http, ctxfrom multiprocessing import Lo
- 5月20日,微软正式提供了Windows XP下可用的雅黑字体下载,雅黑字体是一款近乎完美的字体,解决了宋体小文字无法辩认的问
- Oracle按不同时间分组统计的sql如下表table1: 日期(exportDate) &nbs
- CSS是制作网页效果必不可少的东西,字体的颜色定义、表格的样式定义、图片的特效等等都少不了它。但在Dr
- 实训课期间忙里偷闲的学习了python的selenium包,唯一一点不好是要自己去查英文文档,明摆着欺负我这种英语不好的,想着用谷歌翻译一下
- 在js中调用asp文件的方法很简单,我们可以用在静态页面的点击数统计,虽然静态页面不支持asp程序,但是我们可以使用js调用,来变相的达到这
- 前言1 简介Kepler.gl作为一款强大的开源地理信息数据可视化工具,可以帮助我们轻松制作针对大规模矢量数据的可视化作品,从而辅助数据分析
- Windows 10 x64macOS Sierra 10.12.4Python 2.7准备好装哔~了么,来吧,做个真正意义上的绿色小软件W