Python实现迪杰斯特拉算法并生成最短路径的示例代码
作者：会武术之白猫 发布时间：2023-06-05 21:50:10
标签：Python,迪杰斯特拉算法
def Dijkstra(network,s,d):#迪杰斯特拉算法算s-d的最短路径，并返回该路径和代价
print("Start Dijstra Path……")
path=[]#s-d的最短路径
n=len(network)#邻接矩阵维度，即节点个数
fmax=999
w=[[0 for i in range(n)]for j in range(n)]#邻接矩阵转化成维度矩阵，即0→max
book=[0 for i in range(n)]#是否已经是最小的标记列表
dis=[fmax for i in range(n)]#s到其他节点的最小距离
book[s-1]=1#节点编号从1开始，列表序号从0开始
midpath=[-1 for i in range(n)]#上一跳列表
for i in range(n):
for j in range(n):
if network[i][j]!=0:
w[i][j]=network[i][j]#0→max
else:
w[i][j]=fmax
if i==s-1 and network[i][j]!=0:#直连的节点最小距离就是network[i][j]
dis[j]=network[i][j]
for i in range(n-1):#n-1次遍历，除了s节点
min=fmax
for j in range(n):
if book[j]==0 and dis[j]<min:#如果未遍历且距离最小
min=dis[j]
u=j
book[u]=1
for v in range(n):#u直连的节点遍历一遍
if dis[v]>dis[u]+w[u][v]:
dis[v]=dis[u]+w[u][v]
midpath[v]=u+1#上一跳更新
j=d-1#j是序号
path.append(d)#因为存储的是上一跳，所以先加入目的节点d，最后倒置
while(midpath[j]!=-1):
path.append(midpath[j])
j=midpath[j]-1
path.append(s)
path.reverse()#倒置列表
print(path)
#print(midpath)
print(dis)
#return path
network=[[0,1,0,2,0,0],
[1,0,2,4,3,0],
[0,2,0,0,1,4],
[2,4,0,0,6,0],
[0,3,1,6,0,2],
[0,0,4,0,2,0]]
Dijkstra(network,1,6)
来源：https://www.cnblogs.com/ljy1227476113/p/11720119.html
0
投稿猜你喜欢
- 1引言实现磁带备份数据的功能有两方面的困难：首先，SQL Server（以下简称SQL）所提供的数据库的整体备份及恢复功能不能直接满足本系统
跟着趣味开发python一起实现的弹球小游戏游戏运行效果实现流程1.创建游戏画布（创建ball类）2.增加几个动作（让小球移动、让小球来回反- Python标准库中collections对集合类型的数据结构进行了很多拓展操作，这些操作在我们使用集合的时候会带来很多的便利，多看看很有好
- OpenCV是应用最被广泛的的开源视觉库。他允许你使用很少的代码来检测图片或视频中的人脸。这里有一些互联网上的教程来阐述怎么在OpenCV中
- Laravel重定向分类如下：1、a链接跳转：<a class="btn btn-success" href=&q
- 先给大家快捷总结：文件格式Python库文本文件内置open函数CSV文件csvJSON文件jsonXML文件xml.etree.Eleme
- 一、Json和struct互换（1）Json转struct例子：package main import ( &qu
- SQL Server数据库如何获取TEXT字段的内容长度的方法，是通过DATALENGTH函数来实现的，接下来我们就通过DATALENGTH
- 前言在AI领域，来快速实现一个idea：前后端开发+部署+展现，如果走传统的前后端分离开发+服务器docker部署等方式，会很重且入门成本很
- 标准库的fnmatch库专门用来进行文件名匹配，支持使用通配符进行字符串匹配。1、fnmatch：判断文件名是否符合特定的模式；2、fnma
- 局部名字静态检测 Python探测局部作用域的时候：是在python编译代码时检测，而不是通过他们在运行时的赋值。 正常的情况下，没在函数中
- __str__函数如果定义了该函数，当print当前实例化对象的时候，会返回该函数的return信息可用于定义当前类的描述信息用法:def
- SQL Server判断语句（IF ELSE/CASE WHEN ）执行顺序是 – 从上至下 – 从左至右 --，所当上一个条件满足时（无论
- python对多国语言的处理是支持的很好的，它可以处理现在任意编码的字符，这里深入的研究一下python对多种不同语言的处理。有一点需要清楚
- 首先看一下目标的验证形态是什么样子的是一种通过验证推理的验证方式，用来防人机破解的确是很有效果，但是，But，这里面已经会有一些破绽，比如：
- 哲学上有种说法，“运动是绝对的，静止是相对的”。我们在编写各样的效果时，时常会碰到动画。下面的章，将讨论动画的原理以及实现。动画，简而言之就
- 数据类型描述CHARACTER(n)字符/字符串。固定长度 n。VARCHAR(n) 或 CHARA
- golang1.16也在今天正式发布了。原定计划是2月1号年前发布的，不过迟到也是golang的老传统了，正好也趁着最后的假期快速预览一下g
- 可以把多个页面相同的部分提取出来，放在一个母板里，这些页面只需要继承这个母板就好了通常会在母板中定义页面专用的 CSS 块和 JS 块，方便
- 为了安全起见，最好还是给打开的文件对象指定一个名字，这样在完成操作之后可以迅速关闭文件，防止一些无用的文件对象占用内存。举个例子，对文本文件
