How to find shortest route along with shortest cost in Floyd-Warshal Algorithm

Question

We know Floyd-Warshal algorithm gives us the shortest cost/path to go any node from anyother node.

For example:

From above image we can achieve the below matrix as a result of Floyd-Warshal algo as all pair shortest path(cost)

If you want to go from node 4 to node 3 then there are two ways

• 4 --> 2 --> 3 (cost is 2)
• 4 --> 2 --> 1 --> 3 (cost is 1. So this is shortest route)

From the matrix we are seeing that the value of Row 4 and Column 3 is 1. So this is showing us the shortest cost between these two nodes.

Now my question is -

How can I get the route as well (4-->2-->1-->3) ?

Answer 1

When you have negative edge costs, the trick is to add the absolute value of the smallest cost to every edge ( so that all edges have a zero or positive cost ) In your example, add 2 to every edge cost.

Then the cheapest path can be found in the usual way.