如何更快地计算所有连接节点的总和？

Question

有N个双向连接的节点（Pn），每个节点代表一个值，节点之间有一个衰减值（0 - 1）。现在我想计算从每个节点到每个节点的最大值。 每个节点只计算一次。

可能是我没表达好，我画了一张图

我想计算从每个节点到下一个节点的最大值之和。

然后对所有节点重复。

我的第一个想法是暴力遍历，但我想要一个更快的算法

Answer 1

这个问题有点不简单，因为在这种情况下不能使用否定 Dijkstra 和 Bellman-Ford 算法。我认为解决这个问题的一种方法是使用“旅行商算法”，但不是找到最小路径，而是找到最大值，并跟踪从起点到其他顶点的最大距离。时间复杂度是 O(n!) 所以在较大的图上速度相当慢

from sys import maxsize
from itertools import permutations
 
# implementation of traveling Salesman Problem
def travellingSalesmanProblem(graph, s, distance):
 
    # store all vertex apart from source vertex
    vertex = []
    for i in range(len(graph)):
        if i != s:
            vertex.append(i)
 
    # store maximum weight Hamiltonian Cycle
    max_path = 0
    next_permutation=permutations(vertex)

    for i in next_permutation:
 
        # store current Path weight(cost)
        current_pathweight = 0
 
        # compute current path weight
        k = s
        for j in i:
            current_pathweight += graph[k][j]
            distance[s][j] = max(current_pathweight, distance[s][j])
            k = j
 
        # update minimum
        max_path = max(max_path, current_pathweight)
         
    return max_path, distance
 
 
# Driver Code
if __name__ == "__main__":
 
    # matrix representation of graph
    graph = [[0, 10, 15, 20], [10, 0, 35, 25],
            [15, 35, 0, 30], [20, 25, 30, 0]]

    distance = [[0 for y in range(len(graph))] for x in range(len(graph))]
    for s in range(len(graph)):
        max_path, distance = travellingSalesmanProblem(graph, s, distance)
    
    print(distance)