How to calculate the sum of all connected nodes faster?

Question

There are N bidirectionally connected nodes (Pn), each node represents a value, and there is an attenuation value (0 - 1) between the nodes. Now I want to calculate the maximum value from each node to each node. Each node is calculated only once.

Maybe I didn't express it well, I drew a picture

I want to calculate the sum of the maximum value from each node to a node.

Then repeat to all nodes.

My first thought was brute force traversal, but I'd like to get a faster algorithm

Answer 1

This problem is a bit non-trivial since both negated Dijkstra and Bellman-Ford algorithms can't be used in this case. I think one way to solve this problem is to use the traveling salesman algorithm but instead of finding the minimum path, you find the maximum and also keep track of the maximum distance from the starting point to other vertices (distance in the below code). The time complexity is O(n!) so it's pretty slow on larger graph. Let me know if you attempted a more efficient algorithm

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)