Bellman-Ford 或 Network Flow 用于查找最大数量的不同路径？
Bellman-Ford or Network Flow for findin maximum number of distinct path?
我们有一个有向图（没有权重），G(V, E)，有两个顶点 s 和 t 这样 s 的入度和出度 - t 的度数等于 0。我们想要找到从 s 到 t 的最大单边路径数。通过使用我们可以做到这一点的算法。 Bellman-Ford、Dijkestra、Huffman 和 Network Flow。我认为霍夫曼如此无关紧要，但其他人呢？我认为 Network Flow 是答案，但我不知道为什么？ stackeeeeers，请帮助我！
您可以使用 Network Flow 来完成。它甚至 tells you how on wikipedia:
Maximum edge-disjoint path
Given a directed graph G = (V, E) and two vertices s and t, we are to find the maximum number of edge-disjoint paths from s to t. This problem can be transformed to a maximum flow problem by constructing a network N = (V, E) from G with s and t being the source and the sink of N respectively and assign each edge with unit capacity.
这背后的直觉是，最大流算法在寻找增广路径时基本上解决了您的问题。 this SO question I think, by Ivaylo Strandjev:
中最好地解释了什么是增广路径
An augmenting path is a simple path - a path that does not contain cycles - through the graph using only edges with positive capacity from the source to the sink. So the statement above is somehow obvious - if you can not find a path from the source to the sink that only uses positive capacity edges, then the flow can not be increased(by the way the proof of that statement is not that easy).
我们有一个有向图（没有权重），G(V, E)，有两个顶点 s 和 t 这样 s 的入度和出度 - t 的度数等于 0。我们想要找到从 s 到 t 的最大单边路径数。通过使用我们可以做到这一点的算法。 Bellman-Ford、Dijkestra、Huffman 和 Network Flow。我认为霍夫曼如此无关紧要，但其他人呢？我认为 Network Flow 是答案，但我不知道为什么？ stackeeeeers，请帮助我！
您可以使用 Network Flow 来完成。它甚至 tells you how on wikipedia:
Maximum edge-disjoint path
Given a directed graph G = (V, E) and two vertices s and t, we are to find the maximum number of edge-disjoint paths from s to t. This problem can be transformed to a maximum flow problem by constructing a network N = (V, E) from G with s and t being the source and the sink of N respectively and assign each edge with unit capacity.
这背后的直觉是，最大流算法在寻找增广路径时基本上解决了您的问题。 this SO question I think, by Ivaylo Strandjev:
中最好地解释了什么是增广路径An augmenting path is a simple path - a path that does not contain cycles - through the graph using only edges with positive capacity from the source to the sink. So the statement above is somehow obvious - if you can not find a path from the source to the sink that only uses positive capacity edges, then the flow can not be increased(by the way the proof of that statement is not that easy).