查找两个顶点之间的所有最短路径

Question

给定一个有向图

G=(V,E)

，两个顶点

s

，

t

和两个权重函数

w1

，

w2

，我需要通过

s

找到从

t

到

w2

的最短路径所有的

s

到

t

之间的最短路径为

w1

。 首先，我怎样才能找到两个顶点

s

和

t

之间的所有最短路径？ Dijkstra 算法帮助我们找到从一个顶点到每个其他可访问顶点的最短路径，是否可以修改它以获得两个顶点之间的所有最短路径？

Answer 1

这非常简单。完全来自维基百科：

一个更普遍的问题是找到源和目标之间的所有最短路径（可能有几个长度相同的不同路径）。然后，我们将存储满足松弛条件的所有节点，而不是仅在 previous[] 的每个条目中存储单个节点。例如，如果 r 和 source 都连接到 target，并且它们都位于通过 target 的不同最短路径上（因为两种情况下的边成本相同），那么我们会将 r 和 source 添加到 previous[target]。当算法完成时，先前的[]数据结构实际上将描述一个图，该图是原始图的子集，并删除了一些边。它的关键属性是，如果算法使用某个起始节点运行，那么从该节点到新图中任何其他节点的每条路径都将是原始图中这些节点之间的最短路径，并且该长度的所有路径原始图表将出现在新图表中。然后，为了实际找到两个给定节点之间的所有这些最短路径，我们将在新图上使用路径查找算法，例如深度优先搜索。

换句话说，在 Dijkstra 终止后，您应该能够知道从

s

到

t

的最短路径上的节点的所有先前节点，并使用这些边执行向后 BFS/DFS 将为您提供所有最短路径。

Answer 2

我将扩展对该问题的评论。问题是，对于某些图，两个顶点之间可以有指数数量的最短路径，例如

    o   o         o
   / \ / \       / \
u o   o   o ... o   o v
   \ / \ /       \ /
    o   o         o

这里有

O(2^|V|)

和

u

之间的最短路径。@n.m 提出的方法是更好的方法。在评论中：

只需使用权重函数 w=(w1, w2)，并按分量加法和字典顺序。

字典加法很简单：您定义一个新的权重函数为

v

（即使用给定的两个权重函数的权重向量）。

然后定义加法运算（您必须为权重函数目标集定义一个加法运算）：

w(e)=(w1(e), w2(e))

对于我们的例子：根据权重函数

w = (w1, w2)
W = (W1, W2)
w + W := (w1 + W1, w2 + W2)

，

w = (w1, w2)

，你有一条最短路径。让我们证明这将是根据

p0

的最短路径中根据

w2

的最短路径。基本上，这意味着对于每条路径

w1

p

，这意味着要么

w(p) >= w(p0)

（因此

w1(p) > w1(p0)

不是根据

p

的最短路径）或

w1

和

w1(p) == w1(p0)

，所以路径

w2(p) >= w2(p0) 

是其中之一根据

p

最短，但根据

w1

并不更短。这意味着，根据

w2

，

p0

是根据

w2

最短的当中最短的。

Answer 3

来自

维基百科

：

“Floyd–Warshall 算法比较每对顶点之间通过图的所有可能路径。它能够仅通过图中的 θ(|V|³) 比较来完成此操作。考虑到可能有多达图中的 Ω(|V|²) 条边，并且通过逐步改进对两个顶点之间的最短路径的估计来测试每个边的组合，直到估计达到最佳。”

Answer 4