最短路径

发表于 分类于 阅读次数： 本文字数： 1.6k 阅读时长 ≈ 6 分钟

前言

最短路径算法一般是广搜算法。有多种情况，单源最短路径，多源最短路径，负权回路等问题

多源最短路径Floyd-Warshall算法

  • 优点：实现简单，代码量少
  • 缺点：时间复杂度为O(n^3)，不能解决负权回路的问题

使用邻接矩阵存储法存储图

遍历每个节点作为中转点，取距离的最小值
比如1到3，a[1][3]=6
以2作为中转点，即a[1][2]+a[2][3]=5<a[1][3]

伪代码

1
2
3
4
5
6
7
8
9
10
function floyd(map, length) {
    var i,j,k;
    for(k for 0 to length){//k为中转点，每个点都可以是中转点
        for(i for 0 to length){//起点i
            for(j for 0 to length){//终点j
                map[i][j] = min(map[i][j], map[i][k]+map[k][j]);
            }
        }
    }
}

单源最短路径Dijkstra算法

假设有一个数组 dis[]，存储第一个点能到达的所有点的距离，{0,1,12,∞,∞,∞},
那么, dis[] 就是 第一个点1 到达所有点的最短距离。
dis[] 为 {0,1,12,∞,∞,∞}。

从dis[]数组可以看出, 距离第一个点1最近的点是第二个点2, 将其作为中转点。
再从矩阵map[2][j]中获取所有与第二个点B邻接的点, 即第三个点3和第四个点4,
用dis[j]加上3、4和2的距离，如果小于最小值dis[j], 则更新dis[j]的值。
dis[] 为 {0,1,10,4,∞,∞}。

再找dis[]数组的最小点, 因为点2已经使用过了, 所以选择 点4作为中转点。
dis[] 为 {0,1,8,4,17,19}。

以此类推
以点3作为中转点, dis[] 为 {0,1,8,4,13,19}。
以点5作为中转点, dis[] 为 {0,1,8,4,13,17}。
还剩下最后一个 点6, 没必要找了, 因为没有另一个点可以到达了。

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
47
48
49
public class Main{
  private static int MAX_STEP = 1000;
  public static void main(String[] args) throws Exception {
    Scanner in = new Scanner(System.in);    
    int n = in.nextInt();//顶点数
    int m = in.nextInt();//边数
    int[][] map = new int[n+1][n+1];//存储图的邻接矩阵
    boolean[] book = new boolean[n+1];//标记某个点是否走过
    int[] dis = new int[n+1];//存储最短距离的数组
    for(int i = 1; i <= n; i++) {
      for(int j = 1; j <= n; j++){
        if(i==j) map[i][j] = 0;
        else     map[i][j] = MAX_STEP;
        
      }
    }
    for(int i = 1; i <= m; i++){
      map[in.nextInt()][in.nextInt()] = in.nextInt();
    }
    for(int i = 1; i <= n; i++){
      dis[i] = map[1][i];
    }
    //初始化完毕
    
    book[1] = true;
    for(int i = 1; i <= n-1; i++){//遍历第1到n-1个点
      int min = MAX_STEP;
      int next = 0;
      for(int j = 1; j <=n; j++){//找到距离第i个点最近的一个点作为中转点
        if(book[j]==false && dis[j]<min){
          min = dis[j];
          next = j;
        }
      }
      book[next] = true;
      for(int j = 1; j <= n; j++){//根据中转点获得新的距离，用来更新dis
        dis[j] = Math.min(dis[j], dis[next]+map[next][j]);
      }
      printf(dis);
    }
  }
  
  private static void printf(int[] arr){
    for(int i = 0; i < arr.length; i++){
      System.out.print(arr[i]+" ");
    }
    System.out.println("");
  }
}

另外还有邻接表存储图的算法(看不懂, 弃了)

单源最短路径Bellman-Ford算法

和Dijkstra算法一样, 假设有一个数组 dis[],
存储第一个点能到达的所有点的距离，{0,∞,∞,∞,∞,∞},
那么, dis[] 就是 第一个点0 到达所有点的最短距离。
dis[] 为 {0,∞,∞,∞,∞,∞}, 注意这里和Dijkstra算法不一样。

扫描第一条边0 1 1, 点0 到 点1 的权值为 1。
因为 点0是起点, 所以原先的dis[0]+第一条边的权值w[1]<原先的dis[1], 也就是0+1<∞。
通过第一条边, 可以把 dis[]更新为{0,1,∞,∞,∞,∞}。

扫描第二条边0 2 12, 点0 到 点2 的权值为 12。
因为 点0是起点, 所以原先的dis[0]+第二条边的权值w[2]<原先的dis[2], 也就是0+12<∞。
通过第一条边, 可以把 dis[]更新为{0,1,12,∞,∞,∞}。

扫描第三条边1 2 9, 点1 到 点2 的权值为 9。
因为 点1是起点, 所以原先的dis[1]+第三条边的权值w[3]<原先的dis[2], 也就是1+9<12。
通过第一条边, 可以把 dis[]更新为{0,1,10,∞,∞,∞}。

依次类推,
扫描第4条边1 3 3, dis[]数组 为 {0,1,10,4,∞,∞}。
扫描第5条边2 4 5, dis[]数组 为 {0,1,10,4,15,∞}。
扫描第6条边3 2 4, dis[]数组 为 {0,1,8,4,15,∞}。
扫描第7条边 3 4 13, dis[]数组 为 {0,1,8,4,15,∞}。
扫描第8条边 3 5 15, dis[]数组 为 {0,1,8,4,15,19}。
扫描第9条边4 5 4,dis[]数组 为 {0,1,8,4,15,19}。

第一轮扫描完毕, 一共要扫描 顶点数-1轮。
因为任意两点之间最多包含顶点数-1条边。

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
public class Main {
    public static void main(String[] args) {
        /**
        6 9
        0 1 1
        0 2 12
        1 2 9
        1 3 3
        2 4 5
        3 2 4
        3 4 13
        3 5 15
        4 5 4
        */
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        int[] dis = new int[n]; // 第0个顶点距离其他顶点的距离
        int[] u = new int[m];// 第i条边的起点
        int[] v = new int[m];// 第i条边的终点
        int[] w = new int[m];// 第i条边的权值

        for(int i = 0; i < m; i++){
            u[i] = in.nextInt();
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        dis[0] = 0;
        for(int i = 1; i < n; i++){
            dis[i] = 999;
        }
        // 初始化完毕

        boolean equals = false;
        int[] backupDis = new int[m];

        // 扫描 顶点数-1 轮
        for(int k = 0; k < n-1 && !equals; k++){
            backup(dis, backupDis); // 备份距离数组
            for(int i = 0; i < m; i++){
                dis[v[i]] = Math.min(dis[v[i]], dis[u[i]]+w[i]); // 扫描每条边, 更新dis数组
            }
            equals = equals(dis, backupDis); // 扫描后dis数组是否有变化, 没有则已经是最短路径
        }

        boolean isLoop = false;
        for(int i = 0; i < m && !isLoop; i++){
            if(dis[v[i]] > dis[u[i]]+w[i]){ 
                isLoop = true; // 如果还能继续更新, 说明有负权回路
            }
        }
        System.out.println(isLoop?'有':'无'+"负权回路");

        if(!isLoop){
            System.out.println(Arrays.toString(dis));
        }

    }


    private static void backup(int[] src, int[] backup){
        System.arraycopy(src, 0, backup, 0, src.length);
    }

    private static boolean equals(int[] src, int[] other){
        if(src.length!=other.length) return false;

        for(int i = 0, len = src.length; i < len; i++) {
            if(src[i]!=other[i]) return false;
        }
        return true;
    }
}

总结

算法 单、多源 算法核心 空间复杂度 时间复杂度 适用情况
Floyd-Warshall 多源 中转点 O(N^2) O(N^3) 稠密图, 解决负权回路
Dijkstra 单源 中转点 O(M) O((M+N)logN) 稠密图
Bellman-Ford 单源 边 O(M) O(NM) 稀疏图, 解决负权回路