我要评论一、 迪杰斯特拉算法思想
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)
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持移动技术网。
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论