I have to give the linear program for the widest path problem or maximum capacity path problem which gives the path where the greatest flow is achieved. I thought of solving it as a Max Min problem. First to find all edges that have the minimum value in each possible path from source to destination and second to find the maximum of these values. I don't know how to implement the first part as a linear program. Can anyone help me? If there is another way to solve the problem I will be grateful to know. Thank you in advance!
Asked
Active
Viewed 104 times
0
-
Why it is necessary to find all edges that have the minimum value in each possible path from source to destination? – callculus42 Jun 22 '19 at 20:52
-
For effective combinatorial solutions see https://en.wikipedia.org/wiki/Widest_path_problem – Marcus Ritt Jun 22 '19 at 21:44
-
@callculus Because I have to find the maximum of these minimums and I have to consider all these edges. If my idea of solving this problem is wrong, please correct me. – Kleona Jun 23 '19 at 06:14