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

Question

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):

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

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.

Answer 1

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.