3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

"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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.