数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学Python实现加权图最小成本路径查找程序
假设我们有一个名为edges的二维整数列表，它表示一个无向图。输入中的每一行都表示一条边[u, v, w]，这意味着节点u和v连接，并且边的权重为w。该图包含从0到n-1的n个节点。
路径的成本在此定义为边数与路径中任何边的最大权重的乘积。我们必须找出从节点0到节点n-1的最小可能成本，如果不存在这样的路径，则将答案声明为-1。
So, if the input is like edges = [ [0, 2, 100], [1, 2, 200], [1, 3, 100], [2, 3, 300] ], then the output will be 600
为了解决这个问题，我们将遵循以下步骤：
graph := 新建一个映射
weights := 新建一个映射
max_weight := 0
N := 0
对于edges中的每个u, v, w，执行：
将v插入graph[u]的末尾
将u插入graph[v]的末尾
weights[u, v] := w
weights[v, u] := w
N := N, u + 1, v + 1中的最大值
max_weight := max_weight, w中的最大值
result := 无穷大
当max_weight >= 0时，执行：
d, weight := bfs(0, max_weight)
如果d >= 0，则
result := result, d * weight中的最小值
max_weight := weight - 1
否则，
终止循环
如果result < 无穷大，则返回result，否则返回-1
定义函数bfs()。这将接收root和weight_cap
target := N - 1
Q := 包含root, 0, 0的双端队列
visited := [False] * N
visited[0] := True
当Q不为空时，执行：
v, d, current_weight := 从Q删除最后一个元素
如果v等于N - 1，则
返回d, current_weight
对于graph[v]中的每个w，执行：
如果visited[w]不为零，则
继续下一次迭代
new_weight := weights[v, w]
如果new_weight <= weight_cap，则
visited[w] := True
将(w, d + 1, max(current_weight, 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
zQ.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
665 次浏览
