最近在做最短路径的题目，有几道题是同一个类型的，题意基本都是寻找从A到B所有路径中，路径的最大边的最小值。这样类型的题有POJ - 2253 Frogger， UVA - 10048 Audiophobia，POJ - 1797 Heavy Transportation 这样的题有很多种解题方法，最简单粗暴的就是用Floyd，还可以用Dijkstra，也可以用最小生成树Kruskal 我以POJ - 2253 Frogger这道题作为例子讲讲我对这种题目的理解

题意： 一只青蛙想从A点跳到B点，青蛙可以选择通过不同的点进行跳跃最后到达终点，需要找出所有的路径中两点间距离最大边的最小值 。 理解： 每一条路径都是由多个点构成的，每两个点之间都会有一段距离，在一条路径上找出其中距离最大的那一条边，然后与其他路径的最大边进行比较，找出最大边最小的值 最常规的最短路径中，Floyd和Dijkstra存两点间距离的数组一般都是存两点之间所有路径中互相到达需要的最短路径值，而现在需要存的两点到达需要的最大边的最小值。 以Floyd为例： 常规写法：（比较原来的最小值和通过点k的值哪个小就存哪个）