4

给定一个有向图G=(V,E)、两个顶点s和t两个权重函数w1，w2我需要在 to by 之间的所有最短路径中找到从to by的s最短路径。首先，我怎样才能找到两个顶点和之间的所有最短路径？Dijkstra 的算法帮助我们找到从一个顶点到每个其他可访问顶点的最短路径，是否可以修改它以获得两个顶点之间的所有最短路径？tw2stw1st

4

4 回答 4

2

这是相当直截了当的。完全来自维基百科：

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

换句话说，在 Dijkstra 终止后，您应该能够知道从sto最短路径上的节点的所有先前节点t，并且使用这些边执行反向 BFS/DFS 将为您提供所有最短路径。

于 2013-05-11T14:26:04.730 回答
1

使用动态规划，这可以通过 Floyd-Warshall 算法有效地解决，该算法专门设计用于查找从 s 到 t 的所有可能的最短路径。当您想要处理负边权重时，Floyd-Warshall 确实比 Dijkstra 算法有所改进（Dijkstra 不会处理负权重），但请记住，Floyd-Warshall 算法无法处理负循环。

来自维基百科：

“Floyd–Warshall 算法比较每对顶点之间通过图形的所有可能路径。它能够通过图形中的 Θ(|V|³) 比较来做到这一点。考虑到可能有高达 Ω，这是非常了不起的图中的 (|V|²) 个边，并测试每个边的组合。它通过逐步改进对两个顶点之间的最短路径的估计来做到这一点，直到估计达到最优。

于 2013-05-12T15:01:20.193 回答
1

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

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

这里有和O(2^|V|)之间的最短路径。uv

更好的方法是@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。让我们证明它是根据 的最短路径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是最短的 根据w1。

于 2013-05-11T14:54:17.853 回答
1

Dijkstra 正是您正在寻找的。结果值保存到 Lengths 结构中，其中每个顶点都与一个数值相关联（顶点 s 与可从 x 访问的每个其他顶点之间的距离）。然后只需访问该结构中您的 t 顶点的相应值。搜索实现。它通常就像访问数组的 t 位置一样简单，因为您可以用 int 表示您的顶点。

于 2013-05-17T17:00:45.133 回答