查找最低值顶点到最高值顶点之间最小成本路径的程序（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

开启您的职业生涯

完成课程获得认证

开始学习
广告