多源最短路径--floyd算法

算法作用

floyd用于求单向图的任意两点之间的最短距离，即通过floyd算法计算之后，图的邻接矩阵中每个（I，j）点的权值是最小的。

算法思路

以下面的双向图为例，求每对顶点之间的最短路径。

得到其邻接矩阵，在不经过中间点时，顶点只能到达其邻接点，所以这个矩阵就是其每对顶点的最短路径。

根据经验知道，两点之间的距离经过第三个点可能是会变短的，并且经过的中间点不同可能得到距离更短的点，因此，floyd算法就是依次 比较 以1,2,3，…,n个顶点为中间点之后得到的最终的矩阵的权值，这个矩阵就记录了每对顶点之间相互方向的最短路径。

例如，上图中以顶点1为中间点，这个比较的代码如下

for(int i=0;i<n;i++){
 for(int j=0; j<n;j++){
if(graph[i][j]>graph[i][1]+graph[1][j])；
 }
}

得到的矩阵为

那么要依次比较经过多个中间点的代码就很简单了

for(int k=0;k<n ;k++)//增加一层循环即可
for(int i=0;i<n;i++){
for(int j=0; j<n;j++){
if(graph[i][j]>graph[i][k]+graph[k][j])；
 }
}

由于每经过一个中间点都将距离保存在矩阵中，因此，以第k个中间点时，其实是以k-1个中间点基础上得到的路径距离。

算法实现

因此得到实现代码

package aha_algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Floyd {

static int[][] graph = new int[4][4];
/**
 * @param args
 */
public static void main(String[] args) {
        initGraph();
        floyd();
        System.out.println("最终结果：");
        printGraph();
    }
// 输入图的边，初始化矩阵
static void initGraph() {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
                graph[i][j] = Integer.MAX_VALUE / 3;// 不能溢出
            }
        }
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
for (int i = 0; i < 8; i++) {// 边的条数
try {
                String[] inLine = input.readLine().split(" ");

// 单向图
                graph[Integer.valueOf(inLine[0])][Integer.valueOf(inLine[1])] = Integer.valueOf(inLine[2]);
// graph[Integer.valueOf(inLine[1])][Integer.valueOf(inLine[0])]=1;

            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

static void floyd() {
for (int k = 0; k < 4; k++) {// 增加一层循环即可
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (graph[i][j] > graph[i][k] + graph[k][j])
                        graph[i][j] = graph[i][k] + graph[k][j];
                }
            }
            System.out.println("经过中间点：" + k);
            printGraph();
        }
    }

static void printGraph() {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
                System.out.print(graph[i][j] + " ");
            }
            System.out.println();
        }
    }

}

结果

0 1 1
0 2 5
0 3 3
1 2 2
2 0 6
2 3 1
3 0 5
3 2 11
经过中间点：0
715827882 1 5 3 
715827882 715827882 2 715827882 
6 7 11 1 
5 6 10 8 
经过中间点：1
715827882 1 3 3 
715827882 715827882 2 715827882 
6 7 9 1 
5 6 8 8 
经过中间点：2
9 1 3 3 
8 9 2 3 
6 7 9 1 
5 6 8 8 
经过中间点：3
8 1 3 3 
8 9 2 3 
6 7 9 1 
5 6 8 8 
最终结果：
8 1 3 3 
8 9 2 3 
6 7 9 1 
5 6 8 8 

时间复杂度

时间复杂度为O(n3)

可以用来求简单的指定两点间最短距离和指定点到其余个点的最短距离，即得到floyd的结果矩阵后查矩阵。

floyd不能解决负权环路（注意不是负权边），就是有权值和为负值的环路，这种图是没有最短路径的，每绕一圈都会得到更短的距离的路径。