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

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

2020-09-19 00:20r1-12king Python

这篇文章主要介绍了Python实现迪杰斯特拉算法过程解析,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下

一、迪杰斯特拉算法思想

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到ｉ的最短距离，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)