我需要帮助找到在加权无向图中两个节点之间的所有最短路径。
我能找到使用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
Answer 3:
我遇到过类似的问题，而解决这一https://oj.leetcode.com/problems/word-ladder-ii/
我试图要处理的是先找到使用BFS的最短距离的方式，让说的最短距离为d。 现在申请DFS和DFS递归调用不超越递归水平d。
然而，这可能最终探索由@templatetypedef提到的所有路径。
Answer 4:
首先，找到距离 - 开始使用广度优先搜索所有节点。
（如果有很多节点，你可以使用A *和停止时，队列的顶部有distance-to-start > distance-to-start(end-node) ，这会给你属于一些最短的所有节点路径）
然后，只需从最终节点原路返回。 每当一个节点被连接到两个（或更多）的节点具有较低距离到开始，则分支成两个（或多个）路径。
Answer 5:
templatetypedef你的答案是非常好的，谢谢你很多关于一个（！），但它错过了一点：
如果你有这样的图表：
A-B-C-E-F | | D------
现在，让我们来想象我想这个路径：
A -> E.
这将扩大这样的：
A-> B -> D-> C -> F -> E.
这个问题存在，你会了F-为E的父母，但
A-> B-> D-> FE长于
A-> B-> C->电子。你将不得不采取跟踪父母你这么愉快地加入的距离。
Answer 6:
步骤1：移动由BFS源图表并分配的每个节点从所述源的最小距离
第2步：分配给目标节点之间的距离为最短的长度
步骤3：从源，做沿着其中的最小距离被一个一个增加，直到目标节点的所有路径的DFS搜索达到或达到最短长度。 打印每当到达目标节点的路径。
Answer 7:
当你找到你想要的BFS停止。
你必须修改算法，所以当发现第一路径继续执行。 （删除return语句，并以某种方式保存路径。
你可能最终检查后，执行具有最短路径的结束节点级别的最后一个节点。 （最短路径的所有结束节点是在同一水平）
此外，还有众所周知的算法，找出所有最短路径：
弗洛伊德- Warshall算法 （它有伪代码）
约翰逊的算法
文章来源: Finding all the shortest paths between two nodes in unweighted undirected graph
