查找2點之間的最大路徑

Question

給定無向連接圖，旅行者必須多次從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.

注意圖中可以包含週期，但路徑只能訪問一個節點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 = 0

而且旅行者必須從A前往D - 3 = 2

edge_B_D = 3更新的邊緣值，直到從A到D的所有路徑都具有0值。

Answer 1

您的問題與最大流量/最小切割問題非常相似。由於每條路徑行走的次數由具有最小值的邊確定，所以最大值受到兩個較小頂點集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}}。