I know that there are others library to operate on the graph (eg networkX) but I’m using gviz for other purposes and I need to know if it is possible to calculate the longest path between 2 element of the graph, or also the longest path throughout the graph.
Thank you
The Graphviz package includes the dijkstra program (https://graphviz.org/pdf/dijkstra.1.pdf) that calculates shortest paths, but does not seem to include any tools that provide what you ask for.
1 Like
Interesting. We don’t have that. This is a recent article that should provide some context: Solving the longest simple path problem with heuristic search — Ben-Gurion University Research Portal I wonder about implementations of such heuristics. The important thing wouldn’t be a specific platform (like graphviz, or NetworKit or NetworkX) but a suitable implementation.
1 Like
If I understand this (Longest path problem - Wikipedia) correctly, a simple enhancement to the dijkstra program would provide longest path. Just negate all node-node distances (e.g 2 becomes -2 and 16 becomes -16). Then continue to pick the smallest number (-16 < -2).
It would be wonderful if it were that easy. In general, though, it’s not possible to adapt any algorithm that way - if I’m not mistaken, Dijkstra’s algorithm assumes non-negative weights. The Wikipedia article, though terse, does explain that Longest Path in an undirected graph is an intractable problem, and, disappointingly, there are not even good approximation schemes.
The situation is better with directed graphs. I saw somewhere there are linear time algorithms.