溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
一、 迪杰斯特拉算法思想
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)
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
