前言
全源最短路徑是相對(duì)單源最短路徑而言的，用于查找圖中所有點(diǎn)對(duì)其它點(diǎn)的最短路徑氏仗。
Floyd-Warshall算法適用于存在負(fù)權(quán)重但不存在負(fù)回路的圖吉捶，稠密圖，它的運(yùn)行時(shí)間為O(n3)皆尔。
它的實(shí)質(zhì)是動(dòng)態(tài)規(guī)劃呐舔。
本文以下圖為示例：
最優(yōu)子結(jié)構(gòu)
具體描述為：對(duì)于給定的帶權(quán)圖 G = (V, E)，設(shè) p = <v1, v2, …,vk> 是從 v1 到 vk 的最短路徑慷蠕，那么對(duì)于任意 i 和 j珊拼，1 ≤ i ≤ j ≤ k，pij = <vi, vi+1, …, vj> 為 p 中頂點(diǎn) vi 到 vj 的子路徑流炕，那么 pij 是頂點(diǎn) vi 到 vj 的最短路徑杆麸。
設(shè)帶權(quán)圖 G = (V, E) 中的所有頂點(diǎn) V = {1, 2, . . . , n}搁进，考慮一個(gè)頂點(diǎn)子集 {1, 2, . . . , k}。對(duì)于任意對(duì)頂點(diǎn) i, j昔头，考慮從頂點(diǎn) i 到 j 的所有路徑的中間頂點(diǎn)都來(lái)自該子集 {1, 2, . . . , k}饼问，設(shè) p 是該子集中的最短路徑。Floyd-Warshall 算法描述了 p 與 i, j 間最短路徑及中間頂點(diǎn)集合 {1, 2, . . . , k - 1} 的關(guān)系揭斧，該關(guān)系依賴于 k 是否是路徑 p 上的一個(gè)中間頂點(diǎn)莱革。
設(shè)d(k)ij為從結(jié)點(diǎn)i到結(jié)點(diǎn)j的所有中間結(jié)點(diǎn)全部取自于集合 {1, 2, . . . , k} 的一條最短路徑的權(quán)重。當(dāng)k=0時(shí)讹开，即最短路徑中不包含任何中間結(jié)點(diǎn)盅视，此時(shí)的最短路徑就是權(quán)重本身值。
具體實(shí)現(xiàn)
根據(jù)上文分析旦万，可以遍歷k值闹击，將最短路徑分成兩段，如果pik和pkj之和少于pij成艘，則認(rèn)為k是ij最短路徑上的中間節(jié)點(diǎn)赏半，更新最短路徑值。
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();
}
}
