程序用于找出图中两个顶点之间惩罚最小的路径(Python)
pythonserver side programmingprogramming更新于 2025/12/2 15:40:17
假设我们得到一个无向加权图，并被要求找出从节点 a 到节点 b 惩罚最小的路径。路径的惩罚是路径中所有边的权重的按位或。因此，我们必须找出这样一条"惩罚最小"的路径，如果两个节点之间不存在路径，则返回 -1。
因此，如果输入如下
start (s) = 1, end (e) = 3;那么输出将是 15。
顶点 1 和 3 之间存在两条路径。最佳路径是 1->2->3，路径的成本是 (10 OR 5) = 15。
为了解决这个问题，我们将遵循以下步骤 −
- 定义一个函数 helper() 。这将需要 G、s、e
- v := 一个新集合
- c := 一个大小为 n 的新列表，初始化值为无穷大
- heap := 一个包含对 (0, s) 的新堆
- 当堆的大小 > 0，执行
- cst := 从堆中弹出最小项
- cur := 从堆中弹出最小项
- c[cur] := (cst, c[cur]) 的最小值
- 如果 (cst, cur) 存在于 v 中，则
- 进行下一次迭代
- 如果 cur 与 e 相同，则
- 返回 c[cur]
- 将对 (cst, cur) 添加到 v
- 对于每个邻居，G[cur] 中的 n_cost，执行
- 将值 ((n_cost OR cst), neighbor) 推送到堆
- 返回 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
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
