與傳遞閉包問題 非常相似的一個(gè)問題是，能不能給出一個(gè)矩陣，根據(jù)矩陣可以以時(shí)間代價(jià)O(n)的方式得到在一個(gè)有向代權(quán)圖中任意指定端點(diǎn)之間的最短距離。求的這個(gè)矩陣的問題被稱為每一對(duì)端點(diǎn)間的最小距離問題。
這里采用的是Floyd算法，它與WalShall 算法非常相似：
如果A可以到達(dá)B，距離為x，且C可以到達(dá)A，距離為y，則求得C可以到達(dá)B，距離為 z = x + y，z小于如果c到B的原來的距離，則用z更新矩陣，否則c到B距離維持不變。
和最小路徑算法類似，這里用一個(gè)很大數(shù)字INFINITY來表示兩個(gè)端點(diǎn)之間距離為無窮大的情況，即不通。這里INFINITY＝最大的int值(~(1<<31))。
Floyd.main()提供簡(jiǎn)單的測(cè)試。
與WalShall 一樣，F(xiàn)loyd算法本身的時(shí)間代價(jià)為O(n^3)
代碼如下：
1
class Floyd 
{
2
private int[][] adjMat;
3 private static final int INFINITY = ~(1<<31);
4
5
Floyd(int size) {
6 adjMat = new int[size][size];
7 for(int i=0; i<size; i++)
8 for(int j=0; j<size; j++)
9 adjMat[i][j] = INFINITY;
10
}
11
12 void connect(int from, int to, int length) {
13 adjMat[from][to] = length;
14 }
15
16 void floyd() { //floyd算法
17 for(int y=0; y<adjMat.length; y++) //查找每一行
18 for(int x=0; x<adjMat.length; x++) // 查找每個(gè)單元格
19 if(adjMat[y][x] != INFINITY) //如果 y 可以到達(dá) x
20 for(int z=0; z<adjMat.length; z++) //查找所有行的y列
21 //如果 z 可以到達(dá)y ，說明z
22 //可以直接到達(dá)x,如果算出來的新距離小于原來的距離，則更新
23 if(adjMat[z][y] != INFINITY) {
24 int newLength = adjMat[z][y] + adjMat[y][x];
25 adjMat[z][x] = newLength < adjMat[z][x] ? newLength : adjMat[z][x];
26 }
27
28 }
29
30 int[][] getConnections() {
31 return adjMat;
32 }
33
34 public static void main(String[] args) {
35 Floyd w = new Floyd(5);
36 w.connect(1,0,70);
37 w.connect(2,0,30);
38 w.connect(1,3,10);
39 w.connect(3,2,20);
40 for(int[] a: w.getConnections()) {
41 for(int i: a) System.out.print((i == INFINITY? "INF" : i) + "\t");
42 System.out.println();
43 }
44 w.floyd();
45 System.out.println("==================");
46 for(int[] a: w.getConnections()) {
47 for(int i: a) System.out.print((i == INFINITY? "INF" : i) + "\t");
48 System.out.println();
49 }
50 }
51
}