了解Minimax / Maximin路径（Floyd-Warshall）

Question

我已经实现了弗洛伊德战争算法来解决全对最短路径问题。现在我发现我也可以计算很简单的修改的Minimax或Maximin路径。但我不明白结果意味着什么（最小的路径是什么）。我发现了一些解释在网上，但他们令我困惑。

minimax - 图形中的minimax问题涉及在两个节点之间找到一个路径，最小化路径的最大成本。

maximin - 来自minimax的另一种方式 - 在这里，您有问题在这里需要找到最大化路径最小成本的路径。

有人可以尝试给出另一个解释或一个例子吗？

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!