需要注意的是，请记住，图中两个节点之间的最短路径可能呈指数级增长。任何算法都可能需要指数时间。
也就是说，有一些相对简单的算法可以找到所有路径。这是两个。
BFS+反向DFS
在图上运行广度优先搜索时，您可以用距起始节点的距离来标记每个节点。起始节点的距离为0，然后，每当第一次发现新节点时，它的距离就是发现它的节点的距离加一。因此，首先在图上运行 BFS，记下到每个节点的距离。
一旦你有了这个，你就可以找到a从源到目的地的最短路径如下。从目的地开始，该目的地距起始节点一定距离 d。现在，查看具有进入目标节点的边的所有节点。从源到目的地的最短路径必须沿着从距离 d-1 的节点到距离 d 的目的地的边结束。因此，从目标节点开始，向后穿过某条边到达距离 d-1 处的任何节点。从那里，步行到距离 d-2 处的节点，距离 d-3 处的节点，依此类推，直到回到距离 0 处的起始节点。
此过程将以相反的顺序为您提供一条返回路径，您可以在最后翻转它以获得整体路径。
然后你可以找到all通过从结束节点回到起始节点运行深度优先搜索，从源到目的地的路径，在每个点尝试所有可能的方法从当前节点向后走到距离正好小于 1 的前一个节点当前节点的距离。
（我个人认为这是找到所有可能路径的最简单、最干净的方法，但这只是我的意见。）
多个父母的 BFS
下一个算法是对 BFS 的修改，您可以将其用作预处理步骤，以加速所有可能路径的生成。请记住，当 BFS 运行时，它会按“层”向外进行，获得一条到距离 0 处的所有节点的最短路径，然后是距离 1，然后是距离 2，等等。BFS 背后的动机是，距离 k + 1 处的任何节点从起始节点开始必须通过一条边连接到距起始节点距离为 k 的某个节点。 BFS 通过找到到距离 k 处的节点的长度为 k 的路径，然后通过某个边对其进行扩展，来发现距离为 k + 1 处的该节点。
如果你的目标是找到all最短路径，那么你可以通过扩展来修改BFSevery到距离为 k 的节点到它们连接到的距离为 k + 1 的所有节点的路径，而不是选择单个边。为此，请按以下方式修改 BFS：每当通过在处理队列中添加端点来处理边时，不要立即将该节点标记为已完成。相反，将该节点插入到队列中，并标明您遵循哪条边到达该节点。如果有多个节点链接到该节点，这可能会让您将同一节点多次插入队列中。当您从队列中删除一个节点时，您将其标记为已完成，并且永远不会再次将其插入队列中。同样，您将存储多个父指针，而不是存储单个父指针，每个父指针对应链接到该节点的每个节点。
如果您执行此修改后的 BFS，您最终将得到一个 DAG，其中每个节点要么是起始节点并且没有传出边，要么距离起始节点为 k + 1，并且将有一个指向每个节点的指针它所连接的距离k。从那里，您可以通过列出从您选择的节点回到 DAG 中的起始节点的所有可能路径来重建从某个节点到起始节点的所有最短路径。这可以递归地完成：
- 从起始节点到自身只有一条路径，即空路径。
- 对于任何其他节点，可以通过跟踪每个传出边缘来找到路径，然后递归地扩展这些路径以产生返回到起始节点的路径。
这种方法比上面列出的方法需要更多的时间和空间，因为通过这种方式找到的许多路径不会朝着目标节点的方向移动。不过，它只需要对BFS进行修改，而不是BFS后面再进行反向搜索。
希望这可以帮助！
