找出最小值顶点到最大值顶点之间的最小成本路径的程序(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。

示例

让我们看看以下实现以更好地理解 -

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