查詢圖中兩頂點之間懲罰值最小的路徑的程式（Python）

假設我們給定一個無向加權圖，並要求找出從節點 a 到節點 b 懲罰值最小的路徑。路徑的懲罰值是路徑中所有邊的權重的按位或結果。因此，我們必須找出這樣的“最小懲罰值”路徑，如果兩個節點之間不存在路徑，則返回 -1。

例如，輸入為：

起點 (s) = 1，終點 (e) = 3；則輸出為 15。

頂點 1 和 3 之間存在兩條路徑。最佳路徑是 1->2->3，路徑代價為 (10 或 5) = 15。

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

  • 定義一個函式 helper()。它將接收 G、s、e 作為引數。
    • v := 一個新的集合
    • c := 一個大小為 n 的新列表，初始化值為無窮大
    • heap := 一個新的堆，包含 (0, s) 對
    • 當堆的大小 > 0 時，執行以下操作：
      • cst := 從堆中彈出最小項
      • cur := 從堆中彈出最小項
      • c[cur] := min(cst, c[cur])
      • 如果 (cst, cur) 存在於 v 中，則
        • 進行下一次迭代
      • 如果 cur 等於 e，則
        • 返回 c[cur]
      • 將 (cst, cur) 對新增到 v
      • 對於 G[cur] 中的每個鄰居 n_cost，執行以下操作：
        • 將 ((n_cost 或 cst), neighbor) 推入堆
    • 返回 c[e]
  • G := 包含 n+1 個空列表的新列表
  • 對於 edges 中的每一項，執行以下操作：
    • u := item[0]
    • v := item[1]
    • w := item[2]
    • 將 (v, w) 對插入到 G[u] 的末尾
    • 將 (u, w) 對插入到 G[v] 的末尾
  • ans := helper(G, s, e)
  • 如果 ans 等於無窮大，則返回 -1，否則返回 ans

示例

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

import heapq
from math import inf

def helper(G, s, e):
    v = set()
    c = [inf] * len(G)
    heap = [(0, s)]
    while len(heap) > 0:
        cst, cur = heapq.heappop(heap)
        c[cur] = min(cst, c[cur])
        if (cst, cur) in v:
            continue
        if cur == e:
            return c[cur]
        v.add((cst, cur))
        for neighbor, n_cost in G[cur]:
            heapq.heappush(heap, (n_cost | cst, neighbor))
    return c[e]

def solve(n, edges, s, e):
    G = [[] for _ in range(n + 1)]
    for item in edges:
        u, v, w = map(int, item)
        G[u].append((v, w))
        G[v].append((u, w))
    ans = helper(G, s, e)
    return -1 if ans == inf else ans

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

輸入

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

輸出

15

更新於：2021年10月6日

318 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告