在Python中找到从加权图中的最小成本可能程序

假设我们有一个名为edges的整数二维列表，它是无向图的表示。输入中的每一行表示一条边[u,v,w]，表示节点u和v相连，边的权重为w。图由从0到n-1的n个节点组成。

这里定义路径的成本为边数乘以路径中任何一条边的最大权重。我们必须找出从节点0到节点n-1的最小成本，如果没有这样的路径，则将答案声明为-1。

 因此，如果输入如下，边= [
 [0,2,100]，
 [1,2,200]，
 [1,3,100]，
 [2,3,300]
]，则输出将为600

要解决这个问题，我们将按照以下步骤进行 –

• 新的映射图

• weights := 新的映射

• max_weight := 0

• N := 0

• 对于每个u，v，w in edges，做

  • 将v插入到图[u]的末尾

  • 将u插入到图[v]的末尾

  • weights[u,v] := w

  • weights[v,u] := w

  • N := N，u + 1，v + 1的最大值

  • max_weight := max_weight，w的最大值

• 结果:=无穷大

• while max_weight>=0，do

  • d，weight：= bfs（0，max_weight）

  • 如果 d>=0，则

    • result：= result，d * weight的最小值

    • max_weight：= weight – 1

  • 否则，

    • 终止循环
• 如果结果<无穷大，则返回结果，否则返回-1

• 定义bfs（）函数。 这将采用根，weight_cap

  • target：= N – 1

  • Q：=包含根，0，0的deque

  • visited：= [False] * N

  • visited [0]：= True

  • while Q不为空，do

    • v，d，current_weight: =从Q中删除最后一个元素

    • 如果v与N-1相同，则

    • 返回d，current_weight

    • 对于图中的每个w，do

    • 如果visited [w]为非零，则

      • 继续下一次迭代
    • new_weight：=weights [v，w]

    • 如果new_weight<= weight_cap，则

      • visited [w]：= True

      • 将(w，d + 1，当前权重，new_weight的最大值)添加到Q的左侧

  • 返回-1，-1

例子

让我们看一下以下实现，以更好地理解 –

from collections import defaultdict, deque
class Solution:
    def solve(self, edges):
        graph = defaultdict(list)
        weights = {}
        max_weight = 0
        N = 0
        for u, v, w in edges:
            graph[u].append(v)
            graph[v].append(u)
            weights[u, v] = w
            weights[v, u] = w
            N = max(N, u + 1, v + 1)
            max_weight = max(max_weight, w)
        def bfs(root, weight_cap):
            target = N - 1
            Q = deque([(root, 0, 0)])
            visited = [False] * N
            visited[0] = True
            while Q:
                v, d, current_weight = Q.pop()
                if v == N - 1:
                    return d, current_weight
                for w in graph[v]:
                    if visited[w]:
                        continue
                    new_weight = weights[v, w]
                    if new_weight <= weight_cap:
                        visited[w] = True
                        Q.appendleft((w, d + 1, max(current_weight, new_weight)))
            return -1, -1
        result = float("inf")
        while max_weight >= 0:
            d, weight = bfs(0, max_weight)
            if d >= 0:
                result = min(result, d * weight)
                max_weight = weight - 1
            else:
                break
        return result if result < float("inf") else -1

ob = Solution()
print(ob.solve( [
    [0, 2, 100],
    [1, 2, 200],
    [1, 3, 100],
    [2, 3, 300]
]))

输入

[
    [0, 2, 100],
    [1, 2, 200],
    [1, 3, 100],
    [2, 3, 300]
]

输出

600