Understanding the minimax/maximin paths (Floyd-Warshall)

Question

I've implemented the Floyd-Warshall-Algorithm to solve the All-pairs shortest path problem. Now I found out I can also compute the minimax or maximin path with easy modifications. But I don't understand what the result means (what a minimax path is). I found some explanations on the web, but they are confusing me.

Minimax - Minimax in graph problems involves finding a path between two nodes that minimizes the maximum cost along the path.

Maximin - the other way around from Minimax - here you have problems where you need to find the path the maximizes the minimum cost along a path.

Could someone please try to give an other explanation or an example?

Soto

Answer 1

To understand maximin paths (often called bottleneck paths) in a graph, consider the following problem. You have a road map of a country as a graph where each node represents an intersection and each edge represents a road. Each road has a weight limit, and if you drive a truck that exceeds the limit over that road it will break. You have a truck that you want to drive from some start location to some end location, and you want to put the maximum possible amount of weight on it. Given this, what path should you drive the truck in order to send the maximum possible weight?

If you think about this problem, for any path that you take in the graph, the maximum weight you can send along that path is going to be determined by the edge on that path with the minimum capacity. As a result, you want to find the path from the start to the destination whose minimum-capacity edge is maximized. The path with this property is called the maximin path or bottleneck path, and can be found with a straightforward set of modifications to mot shortest-path algorithms.

The minimax path represents the opposite idea - the path between two points that minimizes the maximum edge capacity.

Hope this helps!

Fording

Indeed. That helped a lot. Especially the 2nd paragraph. Tank you. – Soto

Good example of the minimax is from the wikipedia: "In a graph that represents connections between routers in the Internet, where the weight of an edge represents the bandwidth of a connection between two routers, the widest path problem is the problem of finding an end-to-end path between two Internet nodes that has the maximum possible bandwidth." Look at the image in the wiki link, you will easily understand : ) en.wikipedia.org/wiki/Widest_path_problem – Retaliate