发现两个顶点之间的所有最短路径
给定一个有向图G=(V,E)两个顶点s ， t和两个权重函数w1 ， w2 ，我需要找到从最短路径s到t由w2之间的所有最短路径中s到t由w1 。 首先，我怎么能找到两个顶点s和t之间的所有最短路径？ Dijkstra算法可以帮助我们找到从顶点到其他所有可访问顶点的最短路径，是否可以修改它以获得两个顶点之间的所有最短路径？
我将扩大对这个问题的评论。 问题在于，对于某些图，例如，可以在两个顶点之间有指数数量的最短路径
o o o
/ / /
u o o o ... o o v
/ / /
o o o
这里你在u和v之间有O(2^|V|)最短路径。
@nm在评论中提出了更好的方法：
只需使用一个权重函数w =（w1，w2），以分量方式添加和词典排序。
词典增加很简单：您定义一个新的权重函数为w(e)=(w1(e), w2(e)) （即使用给定的两个权重函数的权重向量）。
然后你定义加法操作（你必须有一个用于加权函数目标集）：
w = (w1, w2)
W = (W1, W2)
w + W := (w1 + W1, w2 + W2)
对于我们的情况：根据权重函数w = (w1, w2) ， p0 w = (w1, w2)您有最短路径。 让我们证明它会按照在最短路径w2按照最短路径中w1 。
基本上，它意味着对于每条路径p w(p) >= w(p0) ，这意味着w1(p) > w1(p0) （因此根据w1 p不是最短的）或w1(p) == w1(p0)和w2(p) >= w2(p0)所以根据w1 ，路径p在最短之中，但根据w2它不是较短的。 这意味着， p0是根据最短w2之间的最短根据w1 。
使用动态编程可以有效解决Floyd-Warshall算法，该算法专门用于查找从s到t的所有可能的最短路径。 当你想处理负边权重时（Dijkstra's不会处理负权重），Floyd-Warshall确实比Dijkstra有改进，但请记住Floyd-Warshall算法不能处理负循环。
维基百科：
“Floyd-Warshall算法比较了每对顶点之间的所有可能的路径图，只需要在图中进行Θ（| V |³）比较就可以做到这一点，考虑到可能存在Ω （| V |²）边，并且测试每个边的组合，这是通过递增地改进两个顶点之间最短路径上的估计来实现的，直到估计值达到最优。
这非常棒。 完全来自维基百科：
更常见的问题是找到源和目标之间的所有最短路径（可能有几个不同长度的路径）。 然后，不是只在前一个[]的每个条目中存储单个节点，而是存储满足松弛条件的所有节点。 例如，如果r和source都连接到目标，并且它们都位于目标的不同最短路径上（因为在这两种情况下边缘开销相同），那么我们会将r和source添加到前一个[target]。 当算法完成时，先前的[]数据结构实际上将描述一个图，该图是原始图的一个子集，其中删除了一些边。 它的关键属性是，如果算法与某个起始节点一起运行，那么从该节点到新图中任何其他节点的每条路径将是原始图中这些节点之间的最短路径，原始图将出现在新图中。 然后为了实际找到两个给定节点之间的所有这些最短路径，我们将在新图上使用路径寻找算法，例如深度优先搜索。
换句话说，在Dijkstra终止之后，您应该能够知道从s到t的最短路径上的所有节点，并且使用这些边进行反向BFS / DFS将为您提供所有最短路径。
上一篇: FInding All Shortest Paths Between Two Vertices
下一篇: Shortest path in an undirected graph that visits k vertices