这种算法有资源吗？
我有一个未加权的图(所有边更精确地为一个容量)，我想找到源顶点和汇点顶点之间的所有不同路径(所有可能的路径，没有人与另一个共享顶点)，所以我想到了最大流量问题和算法，但问题是我想要一个允许我拥有所有最短不同路径的算法。
由于最大流量算法只是在残差图中使用 BFS 或其他东西进行搜索，它会随机增加我的流量(因为权重为 1，最大流量算法的每次迭代都会增加我的流量，这对应于找到一条新的不同路径)，我将以最大数量的不同路径结束，但我无法以最大数量的不同最短路径结束。
最佳答案
要获得最大数量的最短路径，怎么样:
- 首先做一个 BFS 并为每个节点分配一个数字，这将 表示与源的距离。
- 然后删除具有相同编号的节点之间的所有边
- 引导边缘，因此没有流量可以从高值(value)节点移回低值(value)节点
- 运行从源到汇的最大流。
由于没有其他选择，就最短路径而言，最大流总是只需要靠近汇点一步。不可能有任何最短路径在更改后无法找到，因为任何最短路径都必须在每一步中增加它的下一个节点的值，否则就会有另一条更短的路径。
关于algorithm - 最短路径的最大流算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/51439918/