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.