python实现Dijkstra静态寻路算法
作者:By漫步 发布时间:2021-06-10 07:41:09
算法介绍
迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题,算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。
当然目前也有人将它用来处理物流方面,以获取代价最小的运送方案。
算法思路
Dijkstra算法采用的是一种贪心的策略。
1.首先,声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合T。
2.其次,原点 s 的路径权重被赋为 0 (dis[s] = 0)。若对于顶点 s 存在能直接到达的边(s,m),则把dis[m]设为w(s, m),同时把所有其他(s不能直接到达的)顶点的路径长度设为无穷大。初始时,集合T只有顶点s。
3.从dis数组选择最小值,则该值就是源点s到该值对应的顶点的最短路径,并且把该点加入到T中,此时完成一个顶点。
4.再次,看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短,如果是,那么就替换这些顶点在dis中的值。
5.最后,从dis中找出最小值,重复上述动作,直到T中包含了图的所有顶点(可以到达的)。
算法图形演示
现在有图如下:
每个线的权重以及标识如图所示。
第一步:
建立dis数组和T数组。
首先从起点A 开始,将A可以直接到达的顶点的权重记录在dis数组中,无法直达的记录无穷大(当前使用FFFF表示无穷大)。
将当前选择的顶点加入数组T:
第二步:
从dis数组中选择一个不在T数组中的顶点的最小权重值的顶点,当前选择为B顶点,并将B可以直接到达的顶点的相关权重和当前dis中的权重值比较,如果当前dis权重值大,则替换:
将B加入数组T:
第三步:
依次选择顶点C:
将C加入数组T:
第四步:
依次选择顶点D:
将D加入数组T:
第五步:
依次选择顶点E:
将E加入数组T:
第六步:
依次选择顶点F:
将F加入数组T:
因为所有的顶点都已经在T数组中了,算法结束。
这样就求得了从A点到各个顶点的最优解。
可以看到A顶点无法直达F顶点。
代码表示:
(代码中使用999代表FFF)
#encoding:utf-8
import copy
"""
图的表示方式
邻接矩阵
999代表无限远
"""
tuG=[[0, 10, 20, 999, 999, 999],
[999, 0, 999, 20, 70, 999],
[999, 999, 0, 50, 30, 999],
[999, 999, 999, 0, 999, 999],
[999, 999, 999, 10, 0, 999],
[999, 999, 999, 20, 20, 0]];
tuX = 6;
# 设置原点到其他定点的各个距离
dis = copy.deepcopy(tuG[0]);
def Dijkstra(G,v0):
"""
使用 Dijkstra 算法计算指定点 v0 到图 G 中任意点的最短路径的距离
INF 为设定的无限远距离值
"""
t = [];
minv = v0;
while len(t) <= tuX:
t.append(minv);
#以当前点的中心向外扩散
for w in range(0, tuX):
if dis[minv] + G[minv][w] < dis[w]:
dis[w] = dis[minv] + G[minv][w]
tmp = 1000;
for i in range(0, tuX):
tmpFlag = False;
for j in range(0, len(t)):
if i == t[j]:
tmpFlag = True;
break;
if tmpFlag == True:
continue;
if tmp > dis[i]:
tmp = dis[i];
minv = i;
if __name__ == '__main__':
Dijkstra(tuG,0);
print dis;
来源:https://blog.csdn.net/qq_37373203/article/details/82791164
猜你喜欢
- 本文实例为大家分享了python创建tcp服务端和客户端的具体代码,供大家参考,具体内容如下1.服务端serverfrom socket i
- 如何让用户也能修改密码? 好了,照下面添加到你要添加的地方去:<%id = Request(&qu
- 如果你已经理解了block formatting contexts那么请继续,否则请先看看这篇文章。Overflow能够做一些很牛掰的事情,
- 一. Python 的类和实例在面向对象中,最重要的概念就是类(class)和实例(instance),类是抽象的模板,而实例是根据类创建出
- Python爬虫、数据分析、网站开发等案例教程视频免费在线观看https://space.bilibili.com/523606542Sel
- 正则表达式(Regular Expression)为字符串模式匹配提供了一种高效、方便的方法。几乎所有高级语言都提供了对正则表达式的支持,或
- 通过使用turtle绘画象棋棋盘,供大家参考,具体内容如下# 绘制象棋棋盘import turtlet = turtle.Pen()t.wi
- asp之家注:学习javascript(js),免不了要用到打开新窗口,方法很多,总的来说是使用window.open。不同与HTML中的t
- 1. 安装 seaborn安装:pip install seaborn导入:import seaborn as sns2.准备数据正式开始之
- PyTorch与PyTorch Geometric的安装GPU与CUDA,Python,PyTorch的匹配1. 查看Linux系统中GPU
- 如下所示:#coding:utf-8import binasciia = 'worker'#先把worker转换成二进制数据
- 1 简介本篇主要介绍使用pytorch实现基于CharRNN来进行文本分类与内容生成所需要的相关知识,并最终给出完整的实现代码。2 相关AP
- 关于浏览器的最离奇的统计结果之一就是Internet Explorer 版本6,7和8共存。截至本文,Internet Explorer各个
- 对象Javascript 根本上是和对象相关的。数组是对象。函数是对象。对象是对象。那什么是对象呢?对象是名-值对的集合。名是字符串,值可以
- 篇首语:原来改mdb为asp就能防下载是鬼话。 引子:昨天和animator试验了一下,把data.mdb文件改名为data.as
- 在这个星期Doug Bowman离开谷歌的Twitter引发了很多激烈的讨论.在残酷的诚实邮件中,Doug Bowman援引谷歌”限制性的数
- 目录你应该拥有的东西安装开始轻敲截图高级点击TemplateMatching滑动打电话给某人从手机下载文件到电脑手机录屏打开手机发送 Wha
- 前言正则表达式的基础知识就不说了,有兴趣的可以点击这里,提取一般分两种情况,一种是提取在文本中提取单个位置的字符串,另一种是提取连续多个位置
- 本文实例分析了php5.4传引用时报错问题。分享给大家供大家参考,具体如下:php5.3系列版本以及以前版本,传引用没有什么问题,升级到ph
- MySQL扩展库操作MySQL数据库的步骤如下:1:获取连接.2:选取书库。3:设置操作编码。4:发送SQL指令(MySQL数据库可以分为四