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

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内的起始节点的所有可能路径,重建从某个节点到起始节点的所有最短路径.这可以递归完成:

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

希望这可以帮助!

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