查詢最低值頂點到最高值頂點之間最小成本路徑的程式（Python）

假設我們得到一個無向加權圖，並被要求找出從特定節點到另一個特定節點的最小旅行成本路徑。旅行成本計算如下：假設頂點 A 到頂點 C 之間有一條路徑 A->B->C。從 A 到 B 的旅行成本為 10，從 B 到 C 的旅行成本為 20。從 A 到 C 的旅行成本將為 (從 A 到 B 的旅行成本) + (從 B 到 C 的旅行成本與到達節點 B 的累積旅行成本之差)。因此，這將轉換為 10 + (20 - 10) = 20。我們必須在給定圖中找出從第一個節點到最後一個節點（從最小值節點到最大值節點）的最小可能旅行值。

因此，如果輸入如下所示：

則輸出將為 15。

頂點 1 和 4 之間存在兩條路徑。最佳路徑是 1->2->4，路徑成本為 10 + (15 - 10) = 15。否則，路徑成本將為 20。

為了解決這個問題，我們將遵循以下步驟：

  • adjList := 一個包含空列表的新對映
  • 對於edges中的每個專案，執行以下操作：
    • u := item[0]
    • v := item[1]
    • w := item[2]
    • 將 (w,v) 對插入 adjList[u] 的末尾
    • 將 (w,u) 對插入 adjList[v] 的末尾
  • q := 一個新的堆
  • v_list := 一個新的集合
  • 將 (0,1) 插入 q 的末尾
  • flag := True
  • 當 q 不為空時，執行以下操作：
    • c := 從 q 中彈出最小專案
    • 如果 v_list 中存在 c[1]，則
      • 進行下一次迭代
    • 將 c[1] 新增到 v_list
    • 如果 c[1] 與 n 相同，則
      • flag := False
      • 返回 c[0]
    • 對於 adjList[c[1]] 中的每個 u，執行以下操作：
      • 如果 v_list 中不存在 u[1]，則
        • out := max(u[0], c[0] ,u[1])
        • 將 out 推入堆 q
  • 如果 flag 為 True，則
    • 返回 -1

示例

讓我們看看下面的實現以更好地理解：

from collections import defaultdict
import heapq
def solve(n, edges):
    adjList = defaultdict(list)
    for item in edges:
        u, v, w = map(int, item)
        adjList[u].append((w,v))
        adjList[v].append((w,u))
    q = []
    v_list = set()
    q.append((0,1))
    flag = True
    while q:
        c = heapq.heappop(q)
        if c[1] in v_list:
            continue
        v_list.add(c[1])
        if c[1] == n:
            flag = False
            return c[0]
        for u in adjList[c[1]]:
            if u[1] not in v_list:
                out = (max(u[0],c[0]),u[1])
                heapq.heappush(q,out)    
    if flag:
        return -1

print(solve(4, [(1, 2, 10), (2, 3, 5), (2, 4, 15), (1, 4, 20)]))

輸入

4, [(1, 2, 10), (2, 3, 5), (2, 4, 15), (1, 4, 20)]

輸出

15

更新於：2021年10月6日

瀏覽量：359

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告
© . All rights reserved.