algorithm - 有向图中通过某个顶点的最短路径

Question

假设我们有一个具有正边权重的强连通有向图 G (V,E)，并且 V0 属于 V。编写一个算法来找到所有节点对之间通过 V0 的最短路径

一个面试题。显然我们可以使用需要 O(VE) 的 Bellman-Ford。

但是，必须存在更好的解决方案。请问有什么帮助吗？

Answer 1

我认为您甚至可以使用 Dijkstra 的算法。运行一次以找到从 V0 到所有其他顶点的最短路径，然后再次找到从每个其他顶点到 V0 的最短路径（这与在具有反向边的图上运行常规 Dijkstra 相同）。然后对于任何对 (V1,V2) 连接从 V1 到 V0 以及从 V0 到 V2 的路径。