Python實現迪杰斯特拉算法過程解析

def dijkstra(s, used, cost, distance, n):
  distance[s] = 0
  while True:
    # v在這里相當于是一個哨兵，對包含起點s做統(tǒng)一處理！
    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)