如何计算带权顶点图的最短路径？

Question

我正在尝试计算加权顶点的图的最短路径。传统算法如Dijkstra和Floyd-Warshall通常使用加权边，但我没有看到如何将它们应用于我的情况（加权顶点）。我有一个想法是将图转换为具有加权边的更经典视图。这是我收到的结果。在这里，我们有单向和双向加权边，但我仍然不确定哪个算法能够处理以找到最短路径。

- George P.

---

你的解决方案非常好。你具体遇到了什么问题？如果你想知道是否可以使用Dijkstra算法来解决它（一旦转换），那肯定可以。 - Patrice Gahide

好的，那么请参考https://en.wikipedia.org/wiki/Shortest_path_problem#Directed_graphs_with_nonnegative_weights。 - Neil

应该可以工作。基本上你正在做的是：w（u，v）=W_v，其中 W_v 是节点 v 的权重，而 w（u，v） 是转换后图中边 u->v 的权重。只要没有负权重，Dijkstra 算法就是一个不错的选择。请查看此链接以获取最短路径算法的摘要：https://hackernoon.com/shortest-and-longest-path-algorithms-job-interview-cheatsheet-2adc8e18869 - Ari

Answer 1

你可以通过转换图形来实现这一点。 最简单的方法是将每条边转换为一个顶点，并使用与连接它们的原始顶点相同成本的边将新顶点连接在一起。

但是，你真的不需要费心做任何事情...

Dijkstra算法非常容易适应顶点成本，而不需要使用任何这样的转换。 当你遍历一条边时，不是用“new_vertex_cost = old_vertex_cost + edge_weight”，而是用“new_vertex_cost = old_vertex_cost + new_vertex_weight”。

- Matt Timmermans

Answer 2

您可以将问题简化为经典的最短路径问题，并根据需要使用Dijkstra、Bellman-Ford或Floyd-Warshal算法。为了简单起见，在接下来的内容中，我假设所有权重都是非负的。我认为这样的假设是合理的，因为问题提到使用Dijkstra算法来解决问题。最后，可以小心地去除这个假设。

考虑问题的最一般形式：假设G = <V，E>是一个带有边和顶点权重的有向加权图。构造一个只有边权重的图H = <V'，E'>，方法如下：对于G中的任何节点v，在H中创建两个节点v_in和v_out；添加一条权重等于节点v在G中权重的边(v_in -> v_out)。此外，对于G中的任何边(u -> w)，在H中添加一条边(u_out -> w_in)（新边承载与原始边相同的权重）。

总之，对于原始图中的任何顶点，在H中添加两个顶点，一个专门用于入边，另一个专门用于出边（还要根据G中对应顶点的权重连接H中的新相关节点）。

现在，您有一个只有边权重而没有顶点权重的有向加权图H。很容易证明，在H中(s_in，t_out)之间的最短路径与原始图G中(s，t)之间的最短路径相同。

证明基于这样一个事实：任何这样的路径仅在通过H中的边(v_in，v_out)时，相应的路径才会通过节点v在G中。

就分析而言，我们有|V'| = 2|V|，|E'| = |E| + |V|。因此，将问题简化不会影响用于查找最短路径的算法的渐近行为。

- Nima