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

I need help finding all the shortest paths between two nodes in an unweighted undirected graph.

我能找到的使用BFS的最短路径之一，但到目前为止，我迷路了，如何能找到并打印出所有的人。

I am able to find one of the shortest paths using BFS, but so far I am lost as to how I could find and print out all of them.

的算法/伪code任何想法，我可以用？

Any idea of the algorithm / pseudocode I could use?

推荐答案

作为一个警告，记住，可以在图中两个节点之间的指数很多的最短路径。任何算法，这将潜在地指数时间。

As a caveat, remember that there can be exponentially many shortest paths between two nodes in a graph. Any algorithm for this will potentially take exponential time.

这是说，有一个相对简单的修改BFS，您可以使用一个preprocessing一步，加快新一代所有可能的路径。请记住，作为BFS运行，它的收益向外层，得到一个单一的最短路径向所有节点的距离为0，则距离为1，那么距离2等落后BFS的激励的想法是，在距离K + 1中的任何节点从开始节点必须通过边缘被连接到一些节点在从起始节点距离K。 BFS通过寻找长度为k的一些路径，节点的距离K，然后通过一些边缘延伸发现该节点的距离K + 1。

That said, there is a relatively straightforward modification to BFS that you can use as a preprocessing step to speed up generation of all possible paths. Remember that as BFS runs, it proceeds outwards in "layers," getting a single shortest path to all nodes at distance 0, then distance 1, then distance 2, etc. The motivating idea behind BFS is that any node at distance k + 1 from the start node must be connected by an edge to some node at distance k from the start node. BFS discovers this node at distance k + 1 by finding some path of length k to a node at distance k, then extending it by some edge.

如果你的目标是要找到的所有的最短路径，那么你可以通过扩展修改BFS的每次的路径，所有在距离K节点一个节点的距离K + 1，他们连接，而不是选择一个单一的边缘。要做到这一点，修改BFS通过以下方式：只要你过程中加入其端点处理队列中的优势，不要立刻标记节点作为正在做。相反，插入节点与它的边缘，你跟着去它的队列中注明。这将有可能让你插入同一节点插入到队列中的多个时间是否存在链接的多个节点。当您从队列中删除一个节点，那么你将其标记为正在做的，从来没有把它插入到队列中了。同样地，而不是存储一个单亲家庭的指针，你会存储多个父指针，一个用于连接到该节点的每个节点。

If your goal is to find all shortest paths, then you can modify BFS by extending every path to a node at distance k to all the nodes at distance k + 1 that they connect to, rather than picking a single edge. To do this, modify BFS in the following way: whenever you process an edge by adding its endpoint in the processing queue, don't immediately mark that node as being done. Instead, insert that node into the queue annotated with which edge you followed to get to it. This will potentially let you insert the same node into the queue multiple times if there are multiple nodes that link to it. When you remove a node from the queue, then you mark it as being done and never insert it into the queue again. Similarly, rather than storing a single parent pointer, you'll store multiple parent pointers, one for each node that linked into that node.

如果你这样做修改BFS，你会落得一个DAG在每一个节点要么是起始节点，没有出边，或将在距离K + 1从一开始节点，将有一个指针距离k的每个节点，它连接到。从那里，你可以从你选择的节点返回到DAG内的起始节点的所有可能的路径列表重建一些节点的起始节点的所有最短路径。这可以递归实现：

If you do this modified BFS, you will end up with a DAG where every node will either be the start node and have no outgoing edges, or will be at distance k + 1 from the start node and will have a pointer to each node of distance k that it is connected to. From there, you can reconstruct all shortest paths from some node to the start node by listing of all possible paths from your node of choice back to the start node within the DAG. This can be done recursively:

希望这有助于！