d.h*_*ill 6 algorithm graph path minimax floyd-warshall
我已经实现了Floyd-Warshall算法来解决全对最短路径问题.现在我发现我还可以通过简单的修改来计算minimax或maximin路径.但我不明白结果意味着什么(最小极大路径是什么).我在网上找到了一些解释,但它们让我很困惑.
Minimax - 图中问题的Minimax涉及在两个节点之间找到一条路径,以最小化路径上的最大成本.
Maximin - 与Minimax相反的方式 - 在这里你遇到了一些问题,你需要找到最大化路径最小成本的路径.
有人可以尝试给出其他解释或示例吗？
tem*_*def 15
要了解图中的maximin路径(通常称为瓶颈路径),请考虑以下问题.您有一个国家/地区的路线图作为图表,其中每个节点代表一个交叉点,每条边代表一条道路.每条道路都有一个重量限制,如果你驾驶超过该道路限制的卡车,它将会破裂.您有一辆卡车要从一些起始位置开到某个终点位置,并且您想要在其上放置最大可能的重量.鉴于此,您应该驾驶卡车以便发送最大可能的重量？
如果您考虑此问题,对于您在图表中采用的任何路径,您可以沿该路径发送的最大权重将由该路径上具有最小容量的边缘确定.因此,您希望找到从最小容量边缘最大化的起点到目标的路径.具有此属性的路径称为maximin路径或瓶颈路径,可以通过对mot最短路径算法进行简单的修改来找到.
最小极大路径表示相反的想法 - 两点之间的路径,最小化最大边缘容量.
希望这可以帮助!