找出最低价值顶点到最高价值顶点之间的最小成本路径的程序（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：包含空列表的新映射
• 对于边缘中的每个项目，执行
  • 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不为空，就执行以下操作
  • 从q中弹出最小的项c
  • 如果c[1]在v_list中存在，则
    • 进行下一次迭代
  • 将（c[1]）添加到v_list中
  • 如果c[1]与n相同，则
    • flag ：False
    • 返回c[0]
  • 对于c[1]中的每个u，执行以下操作
    • 如果u[1]不在v_list中，则
    • out：（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