Floyd算法:用于多源最短路徑的求解，算出來的是所有的節點到其余各節點之間的最短距離。
該算法的思路是：首先初始化距離矩陣，然后從第一個點開始逐漸更新矩陣點值。d[i][j]表示從i點到j點的距離。第k次更新時，判斷d[i][k]+d[k][j]與d[i][j]的大小，如果前者小，則更新這個值，否則不變。
給一個例子：
具體的floyd實現算法如下[java] view plain copy
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
package com.blyang; public class Floyd { int[][] Matrix; char[] Nodes; private final int INF = Integer.MAX_VALUE; public Floyd(char[] Nodes, int[][] Matrix){ this.Nodes = Nodes; this.Matrix = Matrix; } public void floyd(){ int[][] distance = new int[Nodes.length][Nodes.length]; // 初始化距離矩陣 for(int i=0; i<Nodes.length; i++){ for(int j=0; j<Nodes.length; j++){ distance[i][j] = Matrix[i][j]; } } //循環更新矩陣的值 for(int k=0; k<Nodes.length; k++){ for(int i=0; i<Nodes.length; i++){ for(int j=0; j<Nodes.length; j++){ int temp = (distance[i][k] == INF || distance[k][j] == INF) ? INF : distance[i][k] + distance[k][j]; if(distance[i][j] > temp){ distance[i][j] = temp; } } } } // 打印floyd最短路徑的結果 System.out.printf("floyd: \n"); for (int i = 0; i < Nodes.length; i++) { for (int j = 0; j < Nodes.length; j++) System.out.printf("%12d ", distance[i][j]); System.out.printf("\n"); } } } |
在實現之后，針對上圖的點和權值，給定一個測試：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
package com.blyang; public class Main { public static void main(String[] args) { int INF = Integer.MAX_VALUE; char[] Nodes = {'0', '1', '2', '3'}; int matrix[][] = { /*A*//*B*//*C*//*D*/ /*A*/ { 0, 1, 2, 1}, /*B*/ { INF, 0, INF, INF}, /*C*/ { INF, 3, 0, 1}, /*D*/ { INF, 1, 1, 0}, }; int[] dist = new int[Nodes.length]; Floyd floyd = new Floyd(Nodes, matrix); floyd.floyd(); } } |
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：http://blog.csdn.net/sinat_22013331/article/details/51000331
