Modifying Floyd–Warshall Algorithm for Vertex Weights

Question

I was trying to modify the Floyd–Warshall's algorithm to take into account the weights over the vertices, in addition to the weight of the edges, while computing the shortest path. The length of a path from vertex A to an adjacent vertex B, Path(A,B) , is defined as:

     Vertex_Weight(A) + Edge_Weight(AB) 

For a vertex A:

      Path(A,A) = 0

I was wondering if the Floyd–Warshall can be modified to handle this, and in particular if the following idea will work:

The weight on a vertex V can be added to the weights of all the outgoing edges from V. Thus new edge weight Edge_Weight' is:

      Edge_Weight'(AB) =  Vertex_Weight(A) + Edge_Weight(AB)

One can transform the original graph with the vertex weights to a graph without vertex weights, where the edge weights are modified as above. The normal Floyd–Warshall can be applied now.

If anyone could envisage a scenario where this might not work or if anyone knew of a better way, I would be thankful.

Answer 1

"I was wondering if the Floyd–Warshall can be modified to handle this, and in particular if the following idea will work."

Yes, your cool idea works! In fact, other people have found the same cool technique of including vertex weight in the new edge weight. By the way, I would not say you have modified the Floyd-Warshall algorithm. It is better to say that you have adapted the problem brilliantly so that Floyd-Warshall algorithm can be applied flawlessly.

"If anyone could envisage a scenario where this might not work or if anyone knew of a better way, I would be thankful"

It looks like there is little chance for you to become thankful by that cause.