algorithm - 在未加权无向图中找到两个节点之间的所有最短路径

Question

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

我能够使用BFS找到最短的路径之一，但是到目前为止，我对如何找到并打印所有路径一无所知。

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

Answer 1

需要注意的是，请记住，图中两个节点之间可能存在成倍的最短路径。任何用于此的算法都将花费指数时间。

也就是说，对BFS有一个相对简单的修改，您可以将其用作预处理步骤，以加快所有可能路径的生成。记住，当BFS运行时，它以“层”的形式向外传播，从而到达距离0，然后是距离1，然后是距离2，等等的所有节点的一条最短路径。BFS背后的动机是，距离k + 1的任何节点从起始节点开始的距离必须通过边缘连接到距起始节点距离k处的某个节点。 BFS通过找到到距离为k的某个节点的长度为k的路径，然后将其扩展某个边缘来发现距离为k +1的该节点。

如果您的目标是查找所有最短路径，则可以通过将距离为k的节点的每条路径扩展到与其连接的距离为k + 1的所有节点的方式来修改BFS，而不是选择单个边缘。为此，请按以下方式修改BFS:每当通过在处理队列中添加其端点来处理边缘时，请勿立即将该节点标记为已完成。而是将该节点插入到队列中，并注明要跟随的边缘。如果有多个节点链接到队列，这可能会使您多次将同一节点插入队列。从队列中删除节点时，将其标记为已完成，再也不会将其再次插入队列。同样，您将存储多个父指针，而不是存储单个父指针，每个链接到该节点的节点都将有一个。

如果执行此修改的BFS，则将得到一个DAG，其中每个节点将是起始节点且没有输出边缘，或者与起始节点之间的距离为k + 1，并且将有一个指向该节点的每个节点的指针。它连接到的距离k。从那里，您可以列出从选择的节点到DAG中起始节点的所有可能路径，从而重建从某个节点到起始节点的所有最短路径。这可以递归地完成:

从起始节点到其自身只有一条路径，即空路径。

对于任何其他节点，可以通过跟随每个出站边沿，然后递归扩展这些路径以产生返回起始节点的路径来找到路径。

希望这可以帮助!