algorithm - 寻找最大不同路径数的贝尔曼福特或网络流？

Question

我们有一个有向图（没有权重），G(V, E)，有两个顶点s，t使得 in-degree ofs和 out-degree oft等于0。我们想找到从s到的最大不同边路径数t。通过使用哪种算法，我们可以做到这一点。Bellman-Ford、Dijkestra、Huffman 和 Network Flow。我认为霍夫曼如此无关紧要，但其他人呢？我认为网络流是答案，但我不知道为什么？stackeeeers，请帮助我！

Answer 1

您可以使用网络流来做到这一点。它甚至告诉你如何在维基百科上：

最大边缘不相交路径

给定一个有向图 G = (V, E) 和两个顶点 s 和 t，我们要找到从 s 到 t 的边不相交路径的最大数量。通过从 G 构造一个网络 N = (V, E)，其中 s 和 t 分别是 N 的源和汇，并为每条边分配单位容量，可以将此问题转化为最大流问题。

这背后的直觉是最大流量算法基本上解决了您的问题，同时找到了增广路径。我认为Ivaylo Strandjev在这个 SO 问题中最好地解释了什么是增强路径：

增广路径是一条简单的路径 - 一条不包含循环的路径 - 仅使用从源到汇的具有正容量的边通过图。所以上面的陈述在某种程度上是显而易见的——如果你不能找到一条从源到汇的只使用正容量边的路径，那么就不能增加流量（顺便说一下，该陈述的证明并不那么容易）。