问理解极小极大路径(弗洛伊德-沃尔)

EN

要理解图中的最大化路径(通常称为瓶颈路径)，请考虑以下问题。您有一个国家的路线图作为一个图表，其中每个节点代表一个交叉点，每边代表一条道路。每条路都有一个重量限制，如果你开一辆超过那条路的卡车，它就会坏掉。你有一辆卡车，你想从某个起点开到某个终点，你想把最大的重量放在上面。在这种情况下，你应该驾驶哪条路来运送最大可能的重量？

如果你考虑这个问题，对于图中的任何一条路径，你可以沿着这条路径发送的最大权重将由该路径上具有最小容量的边决定。因此，您希望找到从起点到最小容量边缘最大化的目标的路径。具有此属性的路径称为最大路径或瓶颈路径，可以通过对mot最短路径算法的简单修改找到路径。

minimax路径代表相反的想法--两个点之间的路径，使最大边缘容量最小化。

希望这能有所帮助！