MiniMAX / Maximin Pathsを理解する（Floyd-Warshall）

Question

全ペアの最短経路問題を解決するためのフロイドウォーシェールアルゴリズムを実装しました。今すぐ私は変更が簡単な変更でミニマックスやマキシミンパスを計算することもできます。しかし、私は結果が何を意味するのか理解していません（MiniMaxパスは何ですか）。Web上でいくつかの説明が見つかりましたが、それらは私を混乱させています。

MiniMax - グラフ問題におけるMiniMAXは、経路に沿った最大コストを最小にする2つのノード間の経路を見つけることを含む。

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!