Floyd算法求解最短路径_floyd最短路径算法

1、算法概述

  Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德。

  核心思路：通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。

  算法过程：

• 从任意一条单边路径开始。左右两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。

• 对于每一对顶点u和v，看是否存在一个顶点w使得从u到w再到v比已知的路径更短，如果更短，则更新它。

  上述概念来源于百度百科

2、算法实例

  如下图所示，我们看怎么来求解两点之间的最短路径。

  如果要让任意两点之间(假设是a到b)的路程变短，智能引入第三个点(假设为k)，并通过这个点k进行中转即a->k->b,才可能缩短为原来从顶点a到顶点b的路程。有时候可能不止一个中转点，而是经过两个或者更多的点进行中转会更短。比如上图中的4号和3号之间的路程本来是a[4][3]=12,如果通过1号中转4->1->3，路程将缩短为e[4][1]+e[1][3]=5+6=11。如果同时通过1号和2号中转的话，从4号到3号的路程会进一步缩短为e[4]+e[1][2]+e[2][3]=5+2+3=10。通过以上分析，我们发现每个顶点都有可能使得另外两个顶点之间的路程变短。下面我们模拟该过程。

  我们使用邻接矩阵(二维数组)存储这个图，我们约定自己到自己的路程为0，1号和2号城市的路程为2，则设e[1][2]=2。2号城市无法到达4号城市，设e[2][4]=无穷大我们根据图中的权值得出如下矩阵：

  假设我们现在只允许经过1号顶点中转，求任意两点之间的最短路径。

//经过1号顶点中转
for (int i = 1; i <=N ; i++) {
    for (int j = 1; j <=N; j++) {
        if(e[i][j]>e[i][1]+e[1][j]){
            e[i][j]=e[i][1]+e[1][j];
        }
    }
}
1
2
3
4
5
6
7
8

  此时我们只需要判断e[i][1]+e[1][j]是否比e[i][j]小就行，若小于，更新矩阵。

  由于$e[3][1]+e[1][2]=7+2=9<e[3][2]=\infty$,所以更新矩阵e[3][2]=9

  由于$e[4][1]+e[1][2]=5+2=7<e[4][2]=\infty$,所以更新矩阵e[4][2]=7

  由于$e[4][1]+e[1][3]=5+6=11<e[4][3]=12$,所以更新矩阵e[4][3]=11

  更新后的矩阵如下所示：

  接下来，求只允许经过1号和2号两个顶点的情况下任意两点之间的最短路径。我们需要在只允许经过1号顶点时任意两点的最短路径的结果下，再判断如果经过2号顶点是否可以使得i号顶点到j号顶点之间的路程变得更短，即判断e[i][2]+e[2][j]是否小于e[i][j]。

//经过2号顶点中转
for (int i = 1; i <=N ; i++) {
    for (int j = 1; j <=N; j++) {
        if(e[i][j]>e[i][2]+e[2][j]){
            e[i][j]=e[i][1]+e[1][j];
        }
    }
}
1
2
3
4
5
6
7
8

  由于$e[1][2]+e[2][3]=2+3=5<e[1][3]=6$,所以e[1][3]=5

  由于$e[4][2]+e[2][3]=7+3=10<e[4][3]=11$,所以e[4][3]=10

  以此类推，后面的就不再一个个写了。

  总结：Floyd算法可以算出任意两点的最短路径，可以处理带有负权边的图，但不能处理带有“负环”的图。时间复杂度:$O(n^3)$

3、算法实战

3.1 算法描述

  小明喜欢观景，图示今天来到了蓝桥公园。

  已知公园有N个景点，景点和景点之间一共有M条道路，小明有Q个观景计划。每个计划包含一个起点st和一个终点ed，表示他想从st去到ed。但是小明体力有限，对于每个计划他想走最少的路完成，你可以帮帮他吗？

输入描述

  输入第一行包含三个正整数N,M,Q

  第2到M+1行每行包含三个正整数u,v,w，表示$u\leftrightarrow v$之间存在一条距离为w的路。

  第M+2到M+Q-1行每行包含两个正整数st,ed,其含义如题所述。
$$1\le N\le 400,1\le M\le \frac{N\times (N-1)}{2},Q\le 10^3,1\le u,v,st,ed\le n,1\le w\le 10^9$$
输出描述

  输出共Q行，对应输入数据中的查询。

  若无法从st到达ed则输出-1。

输入输出样例

输入

3 3 3
1 2 1
1 3 5
2 3 2
1 2
1 3
2 3
1
2
3
4
5
6
7

输出

1
3
2
1
2
3

3.2 解题思路

  使用Floyd算法求解，由于该算法时间复杂度为$O(n^3)$，n较大会超时，但是本题的n比较小，所以够用。

  对于图中的任意两个点i和j，我们dist[i][j]表示从i到j的距离。初始时候，对于所有的$1\le i,j\le n$，有$dist[i][j]=\infty$，如果存在边(i,j)，则dist[i][j]=w(i,j)。然后我们用动态规划思想逐步优化dist数组，使得dist[i][j]不断逼近真实的最短路径长度。

  我们主要是维护一个二维数组dist,dist[i][j]表示从i到j的最短路径长度。初始时，如果i和j之间有边，则dist[i][j]为该边(i,j)的权值，否则$dist[i][j]=\infty$。然后从1到n的每个点作为中转点，更新所有可能的最短路径长度。具体的说，对于中转点k，我们遍历所有的i,j，如果dist[i][j]>dist[i][k]+dist[k][j]，则执行更新dist[i][j]=dist[i][k]+dist[k][j]。最后得到的dist数组即为任意两点之间的最短路径长度。

  我们对每个点当作中转点都要做双重for循环,所以在外层再加一个循环，只需要使用三重循环依次枚举中转点k和每对起点i和终点j，并更新dist[i][j]的值即可。

3.3 代码实现

import java.util.Arrays;
import java.util.Scanner;

public class Floyd {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();//N个景点
        int M = scan.nextInt();//经典之间共M条路
        int Q = scan.nextInt();//Q个观景计划
        long[][] dist = new long[N + 1][N + 1];
        for (int i = 1; i <=M ; i++) {  //初始化为最大值
            Arrays.fill(dist[i],Long.MAX_VALUE);
            dist[i][i]=0; //对角线赋值0即可(自己到自己)
        }
        for (int i = 1; i <=M; i++) {  //初始化两点距离
            int u = scan.nextInt();
            int v = scan.nextInt();
            long w = scan.nextLong();
            dist[u][v]=Math.min(dist[u][v],w);
            dist[v][u]=Math.min(dist[v][u],w);
        }
        //Floyd算法
        for (int k = 1; k <=N; k++) {
            for (int i = 1; i <=N ; i++) {
                for (int j = 1; j <=N; j++) {
                    if(dist[i][j]>dist[i][k]+dist[k][j]){
                        dist[i][j]=dist[i][k]+dist[k][j];
                    }
                }
            }
        }
        //查询
        for (int i = 0; i <Q ; i++) {
            int start = scan.nextInt();
            int end = scan.nextInt();
            if(dist[start][end]>=Long.MAX_VALUE){
                System.out.println(-1);
            }else{
                System.out.println(dist[start][end]);
            }
        }
    }
}
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

   真正的算法就5~6行，还是比较好理解的。