寻找从顶点u到v的最短路径，经过顶点w？

Question

在一张有非负边权的有向图中，我可以轻松使用Dijkstra算法找到从u到v的最短路径。但是，是否有任何简单的修改Dijkstra算法的方法，以便我可以通过给定的顶点w找到从u到v的最短路径。或者有其他算法建议吗？

- Pradhan

---

是否有可能找到从u到v的路径，其中包含w，不一定是最短路径。能否在多项式时间内完成，其中n是图中顶点的数量。 - Rahul Kadukar

对于任意图，这个问题是NP难问题。更多细节请参见http://cstheory.stackexchange.com/questions/25077/shortest-path-hitting-a-given-vertex。 - Zach Langley

Answer 1

找到从u到w的最短路径，然后找到从w到v的最短路径。

- Beta

---

这不一定是最短路径。很容易找到一个反例，其中两条最短路径共享一条边。在这种情况下，连接路径并不能给你一个有效的路径。这个问题是NP难的。 - Zach Langley

@ZachLangley：从哪个方面来说它不是一个有效的路径？ - Beta

@Beta 路径不能重复顶点。如果从u到w的最短路径包含顶点z，而从w到v的最短路径也包含z，则在连接的顶点列表中将列出两次z，因此顶点列表不形成路径。事实证明，对于任意有向图，确定是否存在通过w从u到v的任何路径都是NP难问题。（有关更多详细信息，请参见http://cstheory.stackexchange.com/questions/25077/shortest-path-hitting-a-given-vertex。） - Zach Langley

@ZachLangley：谁说路径不能重复顶点？你认为原帖作者有这个条件在考虑吗？ - Beta

@Beta 从问题中并不清楚OP的想法，但是根据我看到的每一个定义，路径不会重复顶点。通常如果允许顶点重复，那么它被称为walk。 - Zach Langley

@ZachLangley：好的，也许“路径”这个词不太合适。 - Beta

Answer 2

1. 从u到w找到最短路径
2. 从w到v找到最短路径

然后，u->w->v就是最短路径。

你可以运行两次Dijkstra算法来完成，但也可以应用Floyd-Warshall算法。

- Mu Qiao

---

看起来这个回答是最完整的；o） - heltonbiker

Answer 3

这个问题是NP难问题，因此找到一个多项式时间的解决方案是不太可能的。请参阅这篇cstheory文章以获取更多详细信息。

- Zach Langley

Answer 4

使用以下方法，我们可以只运行一次算法：

set v_visisted = false
    Start from w and find shortest path to u
    if v was visited during shortest path search to u, set v_visted = true
    If v is part of shortest path from w->u then
          exit with result ( # the path would be u->v->w->v ) 
       else
           if v_visited= true then we already know values for w->v. We have a solution.
           else save path from w->v and switch u to source and find shortest path to v.

请注意，从u到v运行最短路径实际上是继续算法的第一次运行。因此，我们只需通过跟踪是否访问了“v”来运行算法一次即可。

- grdvnl

Answer 5

看起来需要先找到 u 到 w，然后再找到 w 到 v，将两个结果连接起来。这样行得通吗？

- heltonbiker

---

不会的。在最短路径中，有些顶点可能会出现多次。 - Christo S. Christov