0
$\begingroup$

This is referring to not the length of the path, but the sum of the weights of the path traversed. I am getting confused by the variety of algorithms out there.

Suppose that for a graph represented by a dictionary of tuple keys and integer values, my simple idea is to check each pair of nodes to see which nodes connect and simply add up the maximum weight seen so far. I don't know of a better starting point than this.

$\endgroup$
  • 1
    $\begingroup$ are you looking for the longest path? Then that's NP-complete. Or is your graph double-labeled with cost and length, and you always consider the shortest path? If so, what happens if the shortest path isn't unique? $\endgroup$ – John Dvorak Jan 10 '18 at 0:35
  • 1
    $\begingroup$ I'm not looking for the longest path, but rather the path where the weights when summed up gives the maximum value. $\endgroup$ – oldselflearner1959 Jan 10 '18 at 0:36
  • 2
    $\begingroup$ Call your weights "length", and you're down to a well known NP-hard problem. $\endgroup$ – John Dvorak Jan 10 '18 at 0:39
  • 1
    $\begingroup$ If you only talk about shortest paths, what happens if there are multiple paths of the same length, as is a common occurrence in unlabeled graphs? $\endgroup$ – John Dvorak Jan 10 '18 at 0:44
  • 1
    $\begingroup$ Length of a path in a graph is typically not the number of edges in the path, but rather the sum of the "weights" (lengths) of each edge in the path. Finding the longest path is NP-Complete in the general sense as mentioned above. Are there any special properties to your data that might help; e.g. directed/undirected, cyclic/acyclic, actually a tree? More information about the data might help us help you. $\endgroup$ – ryan Jan 10 '18 at 5:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.