图论：多源最短路-Floyd

发表于 更新于 分类于 Artalk： loading...
多源最短路 Floyd

Floyd算法可用来求解多源最短路问题

Floyd

邻接矩阵存储图

nn 表示顶点数量

算法流程

伪代码

1
2
3
4
5
6
7
8
9
10
11
let dist be a |V| × |V| array of minimum distances initialized  ∞ (infinity)
for each vertex v
   dist[v][v] ← 0
for each edge (u,v)
   dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
for k from 1 to |V|
   for i from 1 to |V|
      for j from 1 to |V|
         if dist[i][j] > dist[i][k] + dist[k][j] 
             dist[i][j] ← dist[i][k] + dist[k][j]
         end if

属于动态规划算法，原理较为简单，不再赘述

算法时间复杂度为 O(n3)\Omicron(n^3)

空间占用优化

这里压缩了 distdist 数组的维度，本来应该是 dist[k][i][j]dist[k][i][j] ，表示节点 ii 经过集合 {1,2…k}\{1,2\dots k\} 中的节点到达 jj 的最短路径

转移方程:

dist[k][i][j]=Min{dist[kdist[k][i][j] = Min\{dist[k-1][i][j],dist[k1][i][j], dist[k-1][i][k]+dist[k1][i][k] + dist[k-1][k][j]}1][k][j]\}

即每次比较status: dist[k-1]经过 kk 这个节点和不经过 kk 这个节点的最短路径

复用数组空间，可以将 kk 这一维度去掉，即滚动数组优化

算法证明

由于是动态规划算法，正确性分析，只需保证状态的定义满足「最优子结构」和「无后效性原则」

  • 最优子结构。这个显然，在图中，最短路的子集仍然是最短路径
  • 无后效性。分析之前给出的状态转移方程，可知status: dist[k]完全由status: dist[k-1]转移过来

代码实现

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// initialize g[][]
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
        if (i == j) dist[i][j] = 0;
        else dist[i][j] = INF;
    }
}

//for each edge (u,v)
//   dist[u][v] ← w(u,v)  // the weight of the edge (u,v)

void floyd() {
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
}

java版完整代码

acwing 854. Floyd求最短路

给定一个 nn 个点 mm 条边的有向图，图中可能存在重边和自环，边权可能为负数。

再给定 kk 个询问，每个询问包含两个整数 xx 和 yy，表示查询从点 xx 到点 yy 的最短距离，如果路径不存在，则输出 impossible。

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
import java.util.*;
import java.io.*;

class Main{
    static final int N = 210;
    static final int INF = 0x3f3f3f3f;
    static int[][] dist = new int[N][N];
    static int n, m, k;
    static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static void floyd() {
        for (int k = 1; k <= n; ++k) {
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= n; ++j) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
    public static void main(String[] args) throws Exception {
        String[] str = cin.readLine().split(" ");
        n = Integer.parseInt(str[0]); m = Integer.parseInt(str[1]); k = Integer.parseInt(str[2]);
        // initialize g[][]
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (i == j) dist[i][j] = 0;
                else dist[i][j] = INF;
            }
        }
        int a, b, w;
        while (m-- > 0) {
            str = cin.readLine().split(" ");
            a = Integer.parseInt(str[0]); b = Integer.parseInt(str[1]); w = Integer.parseInt(str[2]);
            dist[a][b] = Math.min(dist[a][b], w);
        }
        floyd();
        while (k-- > 0) {
            str = cin.readLine().split(" ");
            a = Integer.parseInt(str[0]); b = Integer.parseInt(str[1]);
            if (dist[a][b] > INF / 2) log.write("impossible" + '\n');
            else log.write(String.valueOf(dist[a][b]) + '\n');
        }
        
        
        log.flush();
        log.close();
        cin.close();
    }
}

参考资料

📔博文图谱

提及本博文的链接