程序用于找出从最低值顶点到最高值顶点之间的最小成本路径(Python)
pythonserver side programmingprogramming更新于 2025/12/2 16:44:17
假设我们得到一个无向加权图，并被要求找出从特定节点到另一个特定节点的旅行成本最小的路径。旅行成本计算如下:假设顶点 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 := 一个包含空列表的新映射
- 对于边缘中的每个项目，执行
- u := item[0]
- v := item[1]
- w := item[2]
- 在 adjList[u] 末尾插入对 (w,v)
- 在 adjList[v] 末尾插入对 (w,u)
- q := 一个新的堆
- v_list := 一个新的集合
- 在 q 末尾插入 (0,1)
- flag := True
- 当 q 不为空时，执行
- c := 弹出最小项目来自 q
- 如果 c[1] 存在于 v_list 中，则
- 进行下一次迭代
- 将 c[1] 添加到 v_list
- 如果 c[1] 与 n 相同，则
- flag := False
- 返回 c[0]
- 对于 adjList[c[1]] 中的每个 u，执行
- 如果 u[1] 不存在于 v_list 中，则
- out := (u[0], c[0] ,u[1]) 中的最大值
- 推送到堆 q
- 如果 u[1] 不存在于 v_list 中，则
- 如果 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
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
