给定有向图 G=(V,E) ,两个顶点 s , t 和两个权重函数 w1 , w2 ,我需要在 s 之间的 s 到 t 之间的所有最短路径中找到 s 到 t 的最短路径 . 首先,我怎样才能找到两个顶点 s 和 t 之间的所有最短路径? Dijkstra的算法帮助我们找到从顶点到每个其他可访问顶点的最短路径,是否可以修改它以获得两个顶点之间的所有最短路径?
G=(V,E)
s
t
w1
w2
我将扩大对这个问题的评论 . 问题是,对于某些图形,例如,您可以在两个顶点之间具有指数数量的最短路径
o o o / \ / \ / \ u o o o ... o o v \ / \ / \ / o o o
这里 u 和 v 之间有 O(2^|V|) 条最短路径 .
u
v
O(2^|V|)
更好的方法是@n.m提出的方法 . 在评论中:
只需使用权重函数w =(w1,w2),通过分量加法和词典排序 .
词典添加很简单:您将新的权重函数定义为 w(e)=(w1(e), w2(e)) (即使用给定的两个权重函数的权重向量) .
w(e)=(w1(e), w2(e))
然后定义加法运算(你必须有一个加权函数目标集):
w = (w1, w2) W = (W1, W2) w + W := (w1 + W1, w2 + W2)
对于我们的情况:根据权重函数 w = (w1, w2) , p0 ,您有一条最短路径 . 让我们根据 w1 证明它将是根据 w2 中最短路径的最短路径 .
w = (w1, w2)
p0
基本上它意味着对于每个路径 p w(p) >= w(p0) 这意味着 w1(p) > w1(p0) (所以 p 不是 w1 中最短的)或 w1(p) == w1(p0) 和 w2(p) >= w2(p0) 所以路径 p 是根据 w1 最短的路径,但根据 w2 它不短 . 这意味着根据 w1 , p0 是最短的,根据 w2 最短 .
p
w(p) >= w(p0)
w1(p) > w1(p0)
w1(p) == w1(p0)
w2(p) >= w2(p0)
使用动态编程可以使用Floyd-Warshall算法有效地解决这个问题,该算法专门用于查找从s到t的所有可能的最短路径 . 当你想要处理负边缘权重(Dijkstra不会处理负权重)时,Floyd-Warshall确实比Dijkstra有了改进,但请记住,Floyd-Warshall的算法不能处理负周期 .
来自Wikipedia:
“Floyd-Warshall算法比较了每对顶点之间通过图形的所有可能路径 . 只能在图形中使用Θ(| V |³)比较来做到这一点 . 考虑到可能存在图中的Ω(| V |²)边,并且测试了边的每个组合 . 它通过逐步改进两个顶点之间的最短路径上的估计来实现,直到估计是最优的 .
这非常直截了当 . 完全来自Wikipedia:
更普遍的问题是找到源和目标之间的所有最短路径(可能有几个相同长度的不同路径) . 然后,我们将存储满足放松条件的所有节点,而不是仅存储先前[]的每个条目中的单个节点 . 例如,如果r和源都连接到目标,并且它们都位于通过目标的不同最短路径上(因为在两种情况下边缘成本都相同),那么我们将r和源都添加到先前的[目标] . 当算法完成时,先前的[]数据结构将实际描述图形,该图形是原始图形的子集,其中一些边缘被移除 . 它的关键属性是,如果算法是使用某个起始节点运行的,那么从该节点到新图中任何其他节点的每条路径都将是原始图中这些节点之间的最短路径,以及该长度的所有路径 . 原始图表将出现在新图表中 . 然后,为了实际找到两个给定节点之间的所有这些最短路径,我们将在新图上使用路径查找算法,例如深度优先搜索 .
换句话说,在Dijkstra终止之后,您应该能够知道从 s 到 t 的最短路径上的节点的所有先前节点,并且使用这些边缘执行向后BFS / DFS将为您提供所有最短的路径 .
Dijkstra正是您所寻找的 . 结果值将保存到“长度”结构中,其中每个顶点与数值(顶点s和可从x访问的每个其他顶点之间的距离)相关联 . 然后只需访问该结构中t顶点的相应值 . 搜索实现 . 它通常就像访问数组的t位置一样简单,因为你可以用int表示你的顶点 .
4 回答
我将扩大对这个问题的评论 . 问题是,对于某些图形,例如,您可以在两个顶点之间具有指数数量的最短路径
这里
u
和v
之间有O(2^|V|)
条最短路径 .更好的方法是@n.m提出的方法 . 在评论中:
词典添加很简单:您将新的权重函数定义为
w(e)=(w1(e), w2(e))
(即使用给定的两个权重函数的权重向量) .然后定义加法运算(你必须有一个加权函数目标集):
对于我们的情况:根据权重函数
w = (w1, w2)
,p0
,您有一条最短路径 . 让我们根据w1
证明它将是根据w2
中最短路径的最短路径 .基本上它意味着对于每个路径
p
w(p) >= w(p0)
这意味着w1(p) > w1(p0)
(所以p
不是w1
中最短的)或w1(p) == w1(p0)
和w2(p) >= w2(p0)
所以路径p
是根据w1
最短的路径,但根据w2
它不短 . 这意味着根据w1
,p0
是最短的,根据w2
最短 .使用动态编程可以使用Floyd-Warshall算法有效地解决这个问题,该算法专门用于查找从s到t的所有可能的最短路径 . 当你想要处理负边缘权重(Dijkstra不会处理负权重)时,Floyd-Warshall确实比Dijkstra有了改进,但请记住,Floyd-Warshall的算法不能处理负周期 .
来自Wikipedia:
这非常直截了当 . 完全来自Wikipedia:
换句话说,在Dijkstra终止之后,您应该能够知道从
s
到t
的最短路径上的节点的所有先前节点,并且使用这些边缘执行向后BFS / DFS将为您提供所有最短的路径 .Dijkstra正是您所寻找的 . 结果值将保存到“长度”结构中,其中每个顶点与数值(顶点s和可从x访问的每个其他顶点之间的距离)相关联 . 然后只需访问该结构中t顶点的相应值 . 搜索实现 . 它通常就像访问数组的t位置一样简单,因为你可以用int表示你的顶点 .