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があり、旅行者が行かなければならないと言いますからAに変更します。 >B - - >D、及び

edge_A_B = 5

edge_B_D = 3

は、パスの値が

走行経路がAであると仮定min（edge_A_B、edge_B_D）= 3

そして、このパス

edge_A_B = 5走行後 - = 3 3 = 2

edge_B_D - 3 = 0

および旅行者が再びAからDに移動しなければなりませんAからDまでのすべてのパスが0の値になるまでエッジ値を更新しました。

Answer 1

問題は最大フロー/最小カット問題と非常によく似ています。

各パスを歩ける回数は、最小値を持つエッジによって決まるため、最大値は、2つの小さな頂点セット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}}です。