无权无向图中两节点间所有最短路径的求法

Question

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

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

知道我可以使用的算法/伪代码吗？

Answer 1

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

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

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

Answer 2

@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

Answer 3

作为警告，请记住，图中两个节点之间可能存在指数级的多条最短路径。这方面的任何算法都可能需要指数时间。

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

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

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

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

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

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

下一个算法是对BFS的修改，您可以将其用作预处理步骤，以加快所有可能路径的生成。请记住，当BFS运行时，它在“层”中向外前进，在距离0、距离1、距离2等处获得一条通往所有节点的最短路径。BFS背后的激励思想是，距离起始节点k 1的任何节点必须通过边缘连接到距离起始节点k的某个节点。BFS通过找到距离k处的节点的长度为k的路径，然后将其扩展到距离k处的节点，从而发现距离k1处的节点。

如果您的目标是找到所有最短路径，那么您可以通过将距离k处的节点的每个路径扩展到距离k 1处的所有节点来修改BFS，而不是选择一条边。为此，请通过以下方式修改BFS：每当您通过在处理队列中添加其终结点来处理边时，不要立即将该节点标记为已完成。取而代之的是，将该节点插入到队列中，该队列用您遵循的边进行注释。如果有多个节点链接到队列，这可能会让您多次将同一个节点插入队列。当您从队列中删除一个节点时，您将其标记为已完成，并且不再将其插入队列。类似地，您将存储多个父指针，而不是存储单个父指针，每个链接到该节点的节点一个父指针。

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

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

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

希望这能有所帮助！