I have a graph that has both positive and negative weights. Some of the nodes have multiple weights, for example node A has two edges with different weights connected to node B. Can Floyd Warshall algorithm handle this?

I have tried using Bellman Ford, I can calculate the distances but I can't reliably construct the path.

CodePudding user response：

Floyd-Warshall stores edges in a matrix. Therefore, it can't account for multiple edges between a pair of nodes. Still, when constructing the initial matrix, just store the "best" (smallest) edge between each pair.

That said, Bellman-Ford is perhaps more convenient for detecting negative cycles. The reason is that, in Bellman-Ford with negative cycles, the absolute values of distances grow polynomially throughout the algorithm. However, with Floyd-Warshall, they grow exponentially, which will perhaps result in overflow unless extra care is taken at each step.