CODEWITHSUNDEEP
algorithmgraph-theorygraph-algorithm
Monster Hunter
Monster Hunter

Reputation: 866

Find maximum paths between 2 points

Given an undirected connected graph, the traveler has to travel from node A to node B multiple times. Each edge has a positive value and there are multiple paths from node A to node B. The value of a path is defined as the minimum value of all edges in that path. If the traveler goes from node A to node B through a specific path, the value of all edges in the path are decreased by the value of the path (which is minimum value of all edges in that path). 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

As an example, say there are 4 nodes A,B,C,D and the traveler has to go to D from A. Suppose the a path traveled is A->B->D, and

edge_A_B = 5

edge_B_D = 3

Then the value of the path is

min(edge_A_B, edge_B_D) = 3

And after travelling the this path

edge_A_B = 5 - 3 = 2

edge_B_D = 3 - 3 = 0

And the traveler has to travel from A to D again with updated edge values until all paths from A to D has a 0 value.

Upvotes: 0

Views: 234

Answers (1)

Hontaro
Hontaro

Reputation: 83

Your problem is very similar to the Max-Flow/Min-Cut-Problem.

Because the number of times you can walk each path is determined by the edge with the lowest value, the maximum value is limited by the partition ("the cut") of the graph in two smaller vertex sets V and W, while the start node is in V and the end node in W and the values of all edges that go from V to W. This is because to get from start to end, the traveller has to traverse an edge that connects V and W, which means that if those edges have value 0, there are no more paths that the traveller can take

Check this image made by Maxim:

Max-Flow of a graph

The right number represents the value of the edge, the left number represents the flow (or the path travelled in your case). Here, the minimum value of the cut is 5, which is a vertical cut between o and q or q and t. Therefore, the maximum flow (or in your case, the maximum value of all paths travelled) is also 5. Since the value of the incoming flow is equal to the value of the outgoing flow (except for start and end node), it is easy to find the paths he walked afterwards. In this case, it's {{s, o, q, t}, {s, o, q, r, t}, {s, p, r, t}}.

Upvotes: 1

Related Questions