在图中找出两个顶点之间最小惩罚路径的程序（Python）

假设我们有一个无向加权图，并要求从节点a到节点b找出具有最小可能惩罚的路径。路径的惩罚是路径中所有边权的位或。因此，我们必须找到这样一条“最小惩罚”路径，如果两个节点之间不存在路径，则返回-1。

因此，如果输入为

起始点(s) = 1，结束点(e) = 3; 那么输出将为15。

存在两个顶点1和3之间的路径。最优路径是1 -> 2 -> 3，路径的成本是(10 OR 5) = 15。

要解决这个问题，我们将按照以下步骤进行 −

• 定义一个辅助函数helper()。这将带有G、s、e
  • v:=一个新集合。
  • c:=一个新的大小为n的列表，其值为无穷大。
  • heap:=一个包含对(0，s) 的新堆。
  • 当heap的大小>0时，执行以下操作
    • cst:=从heap中弹出最小的项
    • cur:=从heap中弹出最小的项
    • c[cur]:=最小值(cst，c[cur])
    • 如果(cst，cur)出现在v中，则
    • 执行下一次循环。
    • 如果当前等于e，则
    • 返回c[cur]。
    • 将对(cst，cur)添加到v中
    • 对于每个邻居，n_cost在G[cur]中做以下操作
    • 将值((n_cost OR cst)，neighbor)压入heap中。
• 返回 c[e]。
  • G:= [一个包含n + 1个空列表的新列表]
  • 对于每个边缘中的项，执行以下操作
• u:=item[0]

• v:=item[1]
• w:=item[2]
• 在G[u]的最后插入对(v，w)。

• 在G[v]的最后插入对(u，w)。

  • ans:=helper(G，s，e)
  • 如果ans等于inf，则返回-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