一、算法介绍

　　Floyd-Warshall算法（英语：Floyd-Warshall algorithm），中文亦称弗洛伊德算法，是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权（但不可存在负权回路）的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为 O(N³)，空间复杂度为 O(N²)，因时间复杂度比较高，不适合计算大量数据。

二、算法原理

Floyd-Warshall算法的原理是动态规划，Floyd算法适用于APSP(All Pairs Shortest Paths，多源最短路径)。

设 D_i,j,k为从 i 到 j 的只以 (1..k) 集合中的节点为中间节点的最短路径的长度。

若最短路径经过点 k，则 D_i,j,k = D_i,k,k-1 + D_k,j,k-1；
若最短路径不经过点 k，则 D_i,j,k =D_i,j,k-1。

因此，D_i,j,k = min (D_i,j,k-1, D_i,k,k-1 + D_k,j,k-1)。

1         for (k = 0; k < V; k++) {

2             for (i = 0; i < V; i++) {

3                 for (j = 0; j < V; j++) {

4                     if (dist[i][j] > dist[i][k] + dist[k][j]) {

5                         dist[i][j] = dist[i][k] + dist[k][j];

6                     }

7                 }

8             }

9         }

输入矩阵：

1     int[][] graph = {

2                 {0,   5,  INF, 10},

3                 {INF, 0,   3, INF},

4                 {INF, INF, 0,   1},

5                 {INF, INF, INF, 0}

6     };

输出结果：

1 　　Shortest distance matrix :

2       0      5      8      9

3     INF      0      3      4

4     INF    INF      0      1

5     INF    INF    INF      0

　　初始化与输入图矩阵相同的求解矩阵。然后，我们通过将所有顶点视为中间顶点来更新解矩阵。这个思想是一个接一个地选取所有顶点并更新所有最短路径，其中包括所选取的顶点作为最短路径中的中间顶点。

源代码：

 1 package algorithm.shortestpath;

 2

 3 public class AllPairShortestPath {

 4     final static int INF = 99999, V = 4;

 5

 6     public void floydWarshall(int[][] graph) {

 7         int[][] dist = new int[V][V];

 8         int i, j ,k;

 9         for (i = 0; i < V; i++) {

10             for (j = 0; j < V; j++) {

11                 dist[i][j] = graph[i][j];

12             }

13         }

14         for (k = 0; k < V; k++) {

15             for (i = 0; i < V; i++) {

16                 for (j = 0; j < V; j++) {

17                     if (dist[i][j] > dist[i][k] + dist[k][j]) {

18                         dist[i][j] = dist[i][k] + dist[k][j];

19                     }

20                 }

21             }

22         }

23         printSoultion(dist);

24     }

25

26     private void printSoultion(int[][] dist) {

27         System.out.println("The following matrix shows the shortest "+

28                 "distances between every pair of vertices");

29         for (int i = 0; i < V; ++i) {

30             for (int j = 0; j < V; ++j) {

31                 if (dist[i][j] == INF) {

32                     System.out.print("INF ");

33                 } else {

34                     System.out.print(dist[i][j] + "   ");

35                 }

36             }

37             System.out.println();

38         }

39     }

40

41     public static void main(String[] args) {

42         /* 输入带权重矩阵

43                10

44          (0)------->(3)

45           |         /|\

46         5 |          |

47           |          | 1

48          \|/         |

49          (1)------->(2)

50                3           */

51         int[][] graph = {

52                 {0,   5,  INF, 10},

53                 {INF, 0,   3, INF},

54                 {INF, INF, 0,   1},

55                 {INF, INF, INF, 0}

56         };

57

58         AllPairShortestPath a = new AllPairShortestPath();

59

60         a.floydWarshall(graph);

61     }

62 }

巴特西

最短路径算法：弗洛伊德（Floyd-Warshall）算法

一、算法介绍

二、算法原理

最新文章

热门文章