个人中心
gpt4 book ai didi

Python实现迪杰斯特拉算法过程解析

转载 作者：qq735679552 更新时间：2022-09-27 22:32:09 25 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章Python实现迪杰斯特拉算法过程解析由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

1、 迪杰斯特拉算法思想 。

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，所有顶点都包含进来了，算法停止.

2、 具体操作步骤 。

根据其算法思想，确立操作步骤如下:

(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)，直到遍历完所有顶点.

3、代码 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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到ｉ的最短距离，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 。

最后此篇关于Python实现迪杰斯特拉算法过程解析的文章就讲到这里了,如果你想了解更多关于Python实现迪杰斯特拉算法过程解析的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

25 4 0
文章推荐： python使用邻接矩阵构造图代码示例
文章推荐： python先序遍历二叉树问题
文章推荐： 简单了解OpenCV是个什么东西
文章推荐： python的文件操作方法汇总
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com