Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to calculate the shortest path for a graph with weighted vertices?

I’m trying to figure out, how to calculate the shortest path for a graph with weighted vertices. Classical algorithms like Dijkstra and Floyd–Warshall normally work with weighted edges and I'm not seeing a way how to apply them to my case (weighted vertices):

graph with weighted vertices

One of the ideas I had was to convert the graph to the more classical view with weighted edges. This is what I received:

graph with weighted edges

Here we have mono and bi-directional weighted edges, but I'm still not sure which algorithm would handle this in order to find the shortest path.

like image 237
George P. Avatar asked Dec 03 '18 19:12

George P.


1 Answers

You can certainly do this by transforming the graph. The simplest way is to transform each edge into a vertex, and connect the new vertexes together with edges that have the same cost as the vertex that used to join them.

But you don't really need to bother with any of that...

Dijkstra's algorithm is very easy to adapt to vertex costs without using any such transformation. When you traverse an edge, instead of new_vertex_cost = old_vertex_cost + edge_weight, you just do new_vertex_cost = old_vertex_cost + new_vertex_weight.

like image 137
Matt Timmermans Avatar answered Oct 22 '22 17:10

Matt Timmermans