在无权无向图中找到两个节点之间的所有最短路径 [英] Finding all the shortest paths between two nodes in 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.

对我可以使用的算法/伪代码有什么想法吗?

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.

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

That said, there are a few relatively straightforward algorithms that can find all the paths. Here's two.

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

When running a breadth-first search over a graph, you can tag each node with its distance from the start node. The start node is at distance 0, and then, whenever a new node is discovered for the first time, its distance is one plus the distance of the node that discovered it. So begin by running a BFS over the graph, writing down the distances to each node.

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

Once you have this, you can find a shortest path from the source to the destination as follows. Start at the destination, which will be at some distance d from the start node. Now, look at all nodes with edges entering the destination node. A shortest path from the source to the destination must end by following an edge from a node at distance d-1 to the destination at distance d. So, starting at the destination node, walk backwards across some edge to any node you'd like at distance d-1. From there, walk to a node at distance d-2, a node at distance d-3, etc. until you're back at the start node at distance 0.

这个过程会以相反的顺序给你一条返回的路径，你可以在最后翻转它以获得整体路径.

This procedure will give you one path back in reverse order, and you can flip it at the end to get the overall path.

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

You can then find all the paths from the source to the destination by running a depth-first search from the end node back to the start node, at each point trying all possible ways to walk backwards from the current node to a previous node whose distance is exactly one less than the current node's distance.

(我个人认为这是找到所有可能路径的最简单、最干净的方法，但这只是我的意见.)

(I personally think this is the easiest and cleanest way to find all possible paths, but that's just my opinion.)

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

This next algorithm is a 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.

如果您的目标是找到所有最短路径，那么您可以通过将每条路径扩展到距离为 k 的节点到距离为 k + 的所有节点来修改 BFS1 它们连接到，而不是选择单个边缘.为此，请按以下方式修改 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:

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

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

This approach takes more time and space than the one listed above because many of the paths found this way will not be moving in the direction of the destination node. However, it only requires a modification to BFS, rather than a BFS followed by a reverse search.

希望这有帮助！

这篇关于在无权无向图中找到两个节点之间的所有最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！