Python实现迪杰斯特拉算法过程解析
作者:r1-12king 发布时间:2022-08-14 09:55:42
一、 迪杰斯特拉算法思想
Dijkstra算法主要针对的是有向图的单元最短路径问题,且不能出现权值为负的情况!Dijkstra算法类似于贪心算法,其应用根本在于最短路径的最优子结构性质。
最短路径的最优子结构性质:
如果P(i,j)={Vi…Vk…Vs…Vj}是从顶点i到j的最短路径,k和s是这条路径上的一个中间顶点,那么P(k,s)必定是从k到s的最短路径。
证明:
假设P(i,j)={Vi…Vk…Vs…Vj}是从顶点i到j的最短路径,则有P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,s)不是从k到s的最短距离,那么必定存在另一条从k到s的最短路径P(k,s),那么P(i,j)=P(i,k)+P(k,s)+P(s,j)<P(i,j)。则与P(i,j)是从i到j的最短路径相矛盾。因此该性质得证。
因此,Dijkstra算法描述如下:
Dijikstra算法描述如下:
假设存在G=<V,E>,源顶点为V0,S={V0},distance[i]记录V0到i的最短距离,matrix[i][j]记录从i到j的边的权值,即两点之间的距离。
1)从V-S中选择使dist[i]值最小的顶点i,将i加入到U中;
2)更新与i直接相邻顶点的dist值。dist[j]=min{dist[j],dist[i]+matrix[i][j]}
3)直到S=V,所有顶点都包含进来了,算法停止。
二、 具体操作步骤
根据其算法思想,确立操作步骤如下:
(1) 初始时,S只包含起点s;U包含除s外的其他顶点,且U中顶点的距离为"起点s到该顶点的距离"[例如,U中顶点v的距离为(s,v)的长度,然后s和v不相邻,则v的距离为∞]。
(2) 从U中选出"距离最短的顶点k",并将顶点k加入到S中;同时,从U中移除顶点k。
(3) 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离,是由于上一步中确定了k是求出最短路径的顶点,从而可以利用k来更新其它顶点的距离;例如,(s,v)的距离可能大于(s,k)+(k,v)的距离。
(4) 重复步骤(2)和(3),直到遍历完所有顶点。
三、代码
def dijkstra(s, used, cost, distance, n):
distance[s] = 0
while True:
# v在这里相当于是一个哨兵,对包含起点s做统一处理!
v = -1
# 从未使用过的顶点中选择一个距离最小的顶点
for u in range(n):
if not used[u] and (v == -1 or distance[u] < distance[v]):
v = u
if v == -1:
# 说明所有顶点都维护到S中了!
break
# 将选定的顶点加入到S中, 同时进行距离更新
used[v] = True
# 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离,是由于上一步中确定了k是求出最短路径的顶点,从而可以利用k来更新其它顶点的距离;例如,(s,v)的距离可能大于(s,k)+(k,v)的距离。
for u in range(n):
distance[u] = min(distance[u], distance[v] + cost[v][u])
return distance
n, m, T = map(int, input().split())
# 标记数组:used[v]值为False说明改顶点还没有访问过,在S中,否则在U中!
used = [False for _ in range(n)]
# 距离数组:distance[i]表示从源点s到i的最短距离,distance[s]=0
distance = [float('inf') for _ in range(n)]
# cost[u][v]表示边e=(u,v)的权值,不存在时设为INF
cost = [[float('inf') for _ in range(n)] for _ in range(n)]
for _ in range(m):
e = list(map(int, input().split()))
cost[e[0] - 1][e[1] - 1] = e[2]
dis1 = dijkstra(0, used[:], cost, distance[:], n)
d1 = dis1[-1]
dis2 = dijkstra(n-1, used[:], cost, distance[:], n)
d2 = dis2[0]
print((d1+d2)*T)
来源:https://www.cnblogs.com/r1-12king/p/13623885.html
猜你喜欢
- 目录前言1. 使用Lambda来修改Pandas数据框中的值2. 使用f-string来连接字符串3. 用Zip()函数对多个列表进行迭代4
- 原理:建一个栈,每次碰到一个新标签,就与栈顶的标签配对,如果配对,栈顶的标签就出栈,如果不配对,这个新标签就进栈,最终,栈如果是空的,说明所
- What's more important to your web site: pictures or text? If you h
- 这篇博客其实就是这个集合整理后一部分的公开亮相。如果你已经是个python大牛,那么基本上你应该知道这里面的大多数用法了,但我想你应该也能发
- 一般来说,我们判断 iframe 是否加载完成其实与 判断 JavaScript 文件是否加载完成 采用的方法很类似:var&nb
- 科讯5.0 标签和之前版本变化不大,如果用老版本的科讯,可以参考这个标签使用。相关文章:新云4.0 模板通用标签说明 标签清单:======
- 一、安装FastDFS1-1:执行docker命令安装# 安装trackerdocker run -dti --network=host -
- 备注: 关于label和tag,在中文中都翻译成标签,而下文中出现的标签,都是对label的翻译,比如”用户名”+输入框, 这里的”用户名”
- 实例如下:/** * 将数值四舍五入后格式化. * * @pa
- 这篇论坛文章详细介绍了完全卸载MySQL数据库5.0的具体方法,更多内容请参考下文:数据库突然出了问题,没办法只能重装,因为事先并不知道My
- 代码如下:<% sql="select * from serr where
- SQL Server 2008的独到之处:安装SQL Server 2008的设置和安装也有所改进。配置数据和引擎位已经分开了,所以它使创建
- 当变量维数加大时很难想象是怎样按不同维度求和的,高清楚一个,其他的应该就很清楚了,什么都不说了,上例子,例子一看便明白…..a=range(
- 首先说登陆在config.inc.php文件中,有一个选项需要设置查找:$cfg['Servers'][$i]['a
- 一、python判断文件和文件夹是否存在、创建文件夹 >>> import os>>> os.
- Jquery中的一些东西学习一下子,补充完善一下,毕竟有些时候没有使用到这个方式很有用,在使用bootstrap table的时候,选择当前
- excel 文件内容如下:读取excel内容:import xlrdfrom datetime import datetimefrom xl
- 最近有个功能需要java与python之间的数据交互,java需要把参数传给python,然后python计算的结果返回给java.于是就写
- 数组:复制传递(不要按照c/c++的方式去理解,c/c++中数组是引用传递),定长切片:引用传递,底层实现是3个字段 array(数组) +
- <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN&