前言
全源最短路径是相对单源最短路径而言的，用于查找图中所有点对其它点的最短路径。
Floyd-Warshall算法适用于存在负权重但不存在负回路的图，稠密图，它的运行时间为O(n3)。
它的实质是动态规划。
本文以下图为示例：
最优子结构
具体描述为：对于给定的带权图 G = (V, E)，设 p = <v1, v2, …,vk> 是从 v1 到 vk 的最短路径，那么对于任意 i 和 j，1 ≤ i ≤ j ≤ k，pij = <vi, vi+1, …, vj> 为 p 中顶点 vi 到 vj 的子路径，那么 pij 是顶点 vi 到 vj 的最短路径。
设带权图 G = (V, E) 中的所有顶点 V = {1, 2, . . . , n}，考虑一个顶点子集 {1, 2, . . . , k}。对于任意对顶点 i, j，考虑从顶点 i 到 j 的所有路径的中间顶点都来自该子集 {1, 2, . . . , k}，设 p 是该子集中的最短路径。Floyd-Warshall 算法描述了 p 与 i, j 间最短路径及中间顶点集合 {1, 2, . . . , k - 1} 的关系，该关系依赖于 k 是否是路径 p 上的一个中间顶点。
设d(k)ij为从结点i到结点j的所有中间结点全部取自于集合 {1, 2, . . . , k} 的一条最短路径的权重。当k=0时，即最短路径中不包含任何中间结点，此时的最短路径就是权重本身值。
具体实现
根据上文分析，可以遍历k值，将最短路径分成两段，如果pik和pkj之和少于pij，则认为k是ij最短路径上的中间节点，更新最短路径值。
public void floydWashall(MatrixEdge[][] edges){
int n = edges.length;
int[][] d = new int[n][n];
for (int i = 0; i < d.length; i++) {
for (int j = 0; j < d.length; j++) {
if (edges[i][j] != null) {
d[i][j] = edges[i][j].weight;
}else {
if (i == j) {
d[i][j] = 0;
}else {
d[i][j] = 10000;
}
}
}
}
for (int k = 0; k < d.length; k++) {
for (int i = 0; i < d.length; i++) {
for (int j = 0; j < d.length; j++) {
d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(d[i][j] + " ");
}
System.out.println();
}
}
