图（五）：所有顶点间的最短路径
2012-10-18 14:00:43问题描述
对每一对顶点vi ≠ vj，求出vi与vj之间的最短路径和最短路径长度
Floyd算法
Floyd(Floyd-Warshall)算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，该算法名称以创始人之一罗伯特·弗洛伊德命名。
Floyd-Warshall算法是动态规划的一个例子，即该算法中的前面的运算都会给予后面结果一些影响，下一步得出的结果可能会依赖于上一步得出的结果，运算的整个过程需要层层迭代，最终得出结果。
核心思路
松弛技术：对在i和j之间的所有其他点进行一次松弛（寻找中间点）
状态转移方程： map[i][j]=min{map[i][k]+map[k][j],map[i][j]}
具体运算过程
①建立两个辅助数组：
a[ i ][ j ]，存储i到j之间的最小路径长度
path[ i ][ j ]，存储i到j所经历的中间顶点
②辅助数组初始化：使用map[i][j]来进行初始化
若顶点 i能到达顶点 j，使得a[i][j]=map[i][j]，path[i][j] = i
若无法到达，使得a[i][j] = MAX，path[i][j]=-1(作为标记)
③借助状态转移方程对a[][]中所有路径进行松弛
若图有k个顶点，则需遍历k次，使得每个顶点都可用作中间点进行一次松弛判断
核心代码：
for(int k=0; k<sMap.num; k++)
for(int j=0; j<sMap.num; j++)
for(int i=0; i<sMap.num; i++)
④在更新完成之后，所得的两个矩阵即为结果
伪代码实现
