35

我需要帮助找到未加权无向图中两个节点之间的所有最短路径。

我能够使用 BFS 找到最短路径之一，但到目前为止，我不知道如何找到并打印出所有这些路径。

我可以使用的算法/伪代码的任何想法？

4

6 回答 6

34

需要注意的是，请记住，图中两个节点之间的最短路径可能呈指数级增长。任何用于此的算法都可能需要指数级的时间。

也就是说，有一些相对简单的算法可以找到所有路径。这里有两个。

BFS + 反向 DFS

在图上运行广度优先搜索时，您可以标记每个节点与起始节点的距离。起始节点的距离为 0，然后，每当第一次发现一个新节点时，它的距离就是发现它的节点距离的 1 加。因此，首先在图上运行 BFS，记下到每个节点的距离。

一旦你有了这个，你可以找到一条从源到目的地的最短路径，如下所示。从目的地开始，目的地距离起始节点有一段距离。现在，查看所有有边进入目标节点的节点。从源到目的地的最短路径必须通过从距离 d-1 的节点到距离 d 的目的地的一条边结束。因此，从目标节点开始，沿着某个边缘向后走，到达距离 d-1 处您想要的任何节点。从那里步行到距离 d-2 的节点、距离 d-3 的节点等，直到回到距离 0 的起始节点。

此过程将以相反的顺序为您提供一条返回路径，您可以在最后翻转它以获得整体路径。

然后，您可以通过从结束节点回到起始节点运行深度优先搜索来找到从源到目的地的所有路径，在每个点尝试所有可能的方式从当前节点向后走到前一个节点的距离正好比当前节点的距离小一。

（我个人认为这是找到所有可能路径的最简单和最干净的方法，但这只是我的意见。）

有多个父母的 BFS

下一个算法是对 BFS 的修改，您可以将其用作预处理步骤来加速所有可能路径的生成。请记住，当 BFS 运行时，它以“层”的形式向外进行，在距离 0、距离 1、距离 2 等处获得一条最短路径到所有节点。BFS 背后的动机是距离 k + 1 处的任何节点从起始节点必须通过一条边连接到距起始节点距离为 k 的某个节点。BFS 通过找到一条长度为 k 的路径到距离 k 处的节点，然后将其延伸到某个边，从而在距离 k + 1 处发现该节点。

如果您的目标是找到所有最短路径，那么您可以通过扩展每个到距离为 k 的节点的路径到它们连接到的距离为 k + 1 的所有节点，而不是选择一条边。为此，请按以下方式修改 BFS：每当您通过在处理队列中添加其端点来处理边缘时，不要立即将该节点标记为已完成。相反，将该节点插入到队列中，该队列标有您跟随哪个边到达它。如果有多个节点链接到队列，这可能会让您将同一节点多次插入队列。当您从队列中删除一个节点时，您将其标记为已完成，并且不再将其插入队列中。类似地，您将存储多个父指针，而不是存储单个父指针，每个指针用于链接到该节点的每个节点。

如果你做这个修改过的 BFS，你最终会得到一个 DAG，其中每个节点要么是起始节点并且没有出边，要么与起始节点的距离为 k + 1，并且将有一个指向每个节点的指针它连接到的距离k。从那里，您可以通过列出从您选择的节点返回到 DAG 中的起始节点的所有可能路径来重建从某个节点到起始节点的所有最短路径。这可以递归地完成：

  • 从起始节点到自身只有一条路径，即空路径。
  • 对于任何其他节点，可以通过跟随每个传出边找到路径，然后递归地扩展这些路径以产生返回起始节点的路径。

这种方法比上面列出的方法需要更多的时间和空间，因为以这种方式找到的许多路径不会朝着目标节点的方向移动。但是，它只需要对 BFS 进行修改，而不是在 BFS 后进行反向搜索。

希望这可以帮助！

于 2013-01-03T19:15:04.050 回答
5

@templatetypedef 是正确的，但他忘了提到在将任何父链接添加到节点之前必须进行的距离检查。这意味着 se 在每个节点中保持与源的距离，并将子节点的距离增加一。如果孩子已经被访问过并且距离更短，我们必须跳过这个增量和父添加。

public void addParent(Node n) {
    // forbidding the parent it its level is equal to ours
    if (n.level == level) {
        return;
    }
    parents.add(n);

    level = n.level + 1;
}

完整的 java 实现可以通过以下链接找到。

http://ideone.com/UluCBb

于 2015-01-17T14:23:27.453 回答
2

我在解决这个https://oj.leetcode.com/problems/word-ladder-ii/时遇到了类似的问题

我尝试处理的方法是首先使用 BFS 找到最短距离，假设最短距离为 d。现在应用 DFS 并且在 DFS 递归调用中不要超出递归级别 d。

然而，这最终可能会探索@templatetypedef 提到的所有路径。

于 2014-09-11T02:38:51.280 回答
1

首先，使用广度优先搜索找到所有节点的距离。

（如果有很多节点，您可以使用 A* 并在队列顶部有 时停止distance-to-start > distance-to-start(end-node)。这将为您提供属于某个最短路径的所有节点）

然后从端节点回溯。每当一个节点连接到两个（或更多）具有较短起始距离的节点时，您就会分支到两个（或更多）路径。

于 2013-01-03T19:24:08.797 回答
0

templatetypedef 您的回答非常好，非常感谢您的回答（！！），但它错过了一点：

如果你有这样的图表：

ABCEF
  | |
  D-----

现在让我们想象一下我想要这条路：

A -> E。

它将像这样扩展：

A-> B-> D-> C-> F-> E。

存在的问题是，您将 F 作为 E 的父级，但是 

A->B->D->FE
长于

A->B->C->E。
您将不得不跟踪您很高兴添加的父母的距离。

于 2013-09-02T16:41:51.420 回答
0

步骤 1：通过 BFS 从源遍历图，并为每个节点分配到源的最小距离

步骤2：分配给目标节点的距离是最短的长度

第三步：从源头开始，沿着最小距离一一增加的所有路径进行DFS搜索，直到到达目标节点或到达最短长度。每当到达目标节点时打印路径。

于 2018-06-12T06:22:03.487 回答