给定一个无向连通图，旅行者必须多次从节点A到节点B。每条边都有一个正值，并且从 node A 到 node B 有多条路径。路径的值定义为该路径中所有边的最小值。如果旅行者通过特定路径从节点A到节点B，则路径中所有边的值都减少路径值(这是最小值该路径中的所有边缘)。 目标是找到一组路径，使所有经过的路径的值总和最大。
Note the graph may contain cycles but a path can only visit a node
once
例如，假设有 4 个节点 A、B、C、D 和旅行者必须从 A 转到 D。假设a经过的路径是A->B->D，而
edge_A_B = 5
edge_B_D = 3
那么路径的值为
min(edge_A_B, edge_B_D) = 3
走这条路之后
edge_A_B = 5 - 3 = 2
edge_B_D = 3 - 3 = 0
并且旅行者必须再次从 A 到 D 并更新边值，直到从 A 到 D< 的所有路径 的值为 0。
最佳答案
您的问题与Max-Flow/Min-Cut-Problem 非常相似。
因为每条路径可以走的次数由具有最低值的边决定，最大值受限于图在两个较小的顶点集 V 和 W 中的划分(“切割”)，而起始节点在 V 中，结束节点在 W 中，以及从 V 到 W 的所有边的值。这是因为要从头到尾，行者必须遍历连接 V 和 W 的边，这意味着如果这些边的值为 0，那么旅行者就没有更多的路径可以走
检查 Maxim 制作的这张图片:
右边的数字代表边的值，左边的数字代表流(或你的情况下经过的路径)。
这里，割的最小值为5，是o和q或q和t之间的垂直割。因此，最大流量(或者在您的情况下，所有路径的最大值)也是 5。由于传入流量的值等于传出流量的值(开始和结束节点除外)，因此它是很容易找到他后来走过的路。在本例中，它是 {{s, o, q, t}, {s, o, q, r, t}, {s, p, r, t}}。
关于algorithm - 找到两点之间的最大路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38214146/