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
投稿猜你喜欢
- response.getWriter().write() 功能：向前台页面显示一段信息。当在普通的url方式中，会生成一个新的页面来显示内容
- 当需要制作转动鼠标滚轮放大页面字体这样的交互效果时，会用到 Mousewheel 事件。其实在大多数浏览器（IE6, IE7, IE8, O
- 具体代码见下。在此程序中，由于使用了变量，我们需将全部聊友的昵称用“，”（逗号）来隔开，储存到application（"visit
- 一、简介在这篇文章中，我们将学习Python中的高级数据结构，如堆、栈、队列、链表等，并使用Python实现常见的算法，如排序、查找等。我们
- pytorch中训练完网络后，需要对学习的结果进行测试。官网上例程用的方法统统都是正确率，使用的是torch.eq()这个函数。但是为了更精
前言今天制作的这一款能在B站能指定直播间、自动发弹幕的功能的脚本，因为没做那么多的功能，所以代码很简单，适合刚入门的同学学习先打开一个直播间- 02条件语句和while循环三目运算a = 6#原判断语句if a > 5:print(True)else:print(False)#
- 1.腾讯企业邮箱SMTP服务器地址：smtp.exmail.qq.com，ssl端口为：4652.确保腾讯企业邮箱中开启了SMTP服务：3.
- OpenCV：图片缩放和图像金字塔对图像进行缩放的最简单方法当然是调用resize函数啦！resize函数可以将源图像精确地转化为指定尺寸的
- 本文实例讲述了Python实现求最大公约数及判断素数的方法。分享给大家供大家参考。具体实现方法如下：#!/usr/bin/env pytho
- 本文实例为大家分享了基于TensorFlow的CNN实现Mnist手写数字识别的具体代码，供大家参考，具体内容如下一、CNN模型结构输入层：
- 随着网站访问量的加大，每次从数据库读取都是以效率作为代价的，很多用ACCESS作数据库的更会深有体会，静态页加在搜索时，也会被优先考虑。互联
- 目录一、介绍二、前提三、get的请求3.1 GET无参请求3.2 GET传参四、post请求五、Requests响应六、Request扩充七
- 1 如何在网页中获取 JSON 数据？打开一个具有动态渲染的网页，按 F12 打开浏览器开发工具，点击“网络&r
- 前言：本篇主要讲两方面，错误和异常以及模块。在编程时遇见错误信息在所难免，Python中会也有很多种错误信息，常见的两种就是语法错误和逻辑错
- 初学Python，在网上看到Python图片转字符画的教程，我也来尝试下。 首先我们要用到Python的PIL库的Image模块，PIL(P
- 一、简介Paramiko模块是基于Python实现的SSH远程安全连接，用于SSH远程执行命令、文件传输等功能。安装模块默认Python没有
- 学习目的： 学习ADO.NET用法，并如何用DataRearder读取数据 今天练习数据库的最基本用法，如何打开数据库。首先在网站设置文件w
- 例1import osprint 'Process (％s) start...' ％os.getpid()pid = os.
- 在查询语句中使用 NOLOCK 和 READPAST 处理一个数据库死锁的异常时候，其中一个建议就是使用 NOLOCK 或者 READPAS
