如何计算具有加权顶点的图的最短路径？

Question

我想弄清楚，如何计算具有加权顶点的图形的最短路径。Dijkstra 和 Floyd-Warshall 等经典算法通常使用加权边，我没有看到如何将它们应用于我的案例（加权顶点）：

我的想法之一是将图形转换为带有加权边的更经典的视图。这是我收到的：

这里我们有单向和双向加权边，但我仍然不确定哪种算法会处理这个以找到最短路径。

Answer 1

您当然可以通过转换图形来做到这一点。最简单的方法是将每条边转换为一个顶点，然后将新顶点与与用于连接它们的顶点具有相同成本的边连接在一起。

但你真的不需要为这些而烦恼......

Dijkstra 的算法很容易适应顶点成本，而无需使用任何此类转换。当你穿越边缘，而不是new_vertex_cost = old_vertex_cost + edge_weight，你只是做new_vertex_cost = old_vertex_cost + new_vertex_weight。