找到两点之间的最大路径
Find maximum paths between 2 points
给定一个无向连通图，旅行者必须多次从 node A 旅行到 node B。每条边都有一个正值，从 node A 到 node B 有多个路径。路径的值定义为该路径中所有边的最小值。如果旅行者通过特定路径从 node A 到 node B，则路径中所有边的值都会减少该路径的值（这是该路径中所有边的最小值）。 The goal is to find the set of paths that give the maximum sum of values of all paths traveled.
Note the graph may contain cycles but a path can only visit a node once
例如，假设有 4 个节点 A、B、C、D，旅行者必须从 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 和中的分区 ("the cut") 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}}.
给定一个无向连通图，旅行者必须多次从 node A 旅行到 node B。每条边都有一个正值，从 node A 到 node B 有多个路径。路径的值定义为该路径中所有边的最小值。如果旅行者通过特定路径从 node A 到 node B，则路径中所有边的值都会减少该路径的值（这是该路径中所有边的最小值）。 The goal is to find the set of paths that give the maximum sum of values of all paths traveled.
Note the graph may contain cycles but a path can only visit a node
once
例如，假设有 4 个节点 A、B、C、D，旅行者必须从 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 和中的分区 ("the cut") 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}}.