离散数学：最短路的代码实现

众所周知离散课本 204 页 17 题让用 Dijkstra 和 Floyd 求一个 9 个结点的图的最短路径。2025 年 3 月 18 日上午，我抄了一节史纲课的 Dijkstra 过程和 Floyd 的邻接矩阵，心中愤懑不平。于是中午回宿舍猛敲代码零点几秒就把全部都过程都输出出来了，遂把代码打包跟离散作业一起交上去了。

但是这样还不够，写的代码还能再水一篇博客（虽然不会有人看😭）

图的存储#

手敲#

最好是把边一条一条敲出来，格式如 x y w，表示 x 和 y 间有一条边权为 w 的边(这道题是无向边).

dat.txt

标出来点数和边数方便程序读。

电脑存#

Dijkstra 最好用邻接表——说白了就是开 n 个单链表，可以用 C++ 的 vector 或者 Python 的 list 模拟，好处是占用相对邻接矩阵较小，而且遍历方便，适合不那么稠密的图。
Floyd 只能用邻接矩阵，因为 Floyd 算法就是在矩阵上定义的。

算法实现#

这里暂时以书上的描述为准，方便理解。本地有 C++ 环境的话可以自己跑一下玩玩。实际上 Floyd 比 Dijkstra 好写很多，和直觉是相反的。

Dijkstra#

dijkstra.cpp

1
#include <iostream>
2
#include <cstring>
3
#include <vector>
4

5
using namespace std;
6

7
const int N = 10;
8
vector<pair<int, int>> ed[N]; // 边表，存边
9
int d[N];
10
bool inP[N]; // 标记是否在 P 集合中
11

12
int main() {
13
    // 从 dat.txt 中读取数据
14
    freopen("dat.txt", "r", stdin);
15
    freopen("out_dij.txt", "w", stdout);
16
    int n, m;
17
    cin >> n >> m;
18
    for (int i = 1; i <= m; ++i) {
19
        int x, y, z;
20
        cin >> x >> y >> z;
21
        // 两条有向边模拟无向边
22
        ed[x].push_back({z, y});
23
        ed[y].push_back({z, x});
24
    }
25

26
    // 初始化距离为无穷大
27
    memset(d, 0x3f, sizeof(d));
28
    d[1] = 0;
29

30
    for (int i = 1; i <= n; ++i) {
31
        // 寻找加入 P 集合的点
32
        int x = 0;
33
        for (int j = 1; j <= n; ++j) {
34
            if (d[j] < d[x] && !inP[j]) x = j;
35
        }
36
        inP[x] = true;
37

38
        // 用这个点更新其他相连的 T 集合中的点
39
        for (auto [v, y] : ed[x]) {
40
            if (!inP[y]) d[y] = min(d[y], d[x] + v);
41
        }
42

43
        // 输出过程中的 P 集合，T 集合和 d 数组
44
        cout << "round " << i << endl;
45
        cout << "*****************************" << endl;
46
        cout << "P : ";
47
        for (int i = 1; i <= n; ++i) {
48
            if (inP[i]) cout << i << ' ';
49
        }
50
        cout << endl;
51
        cout << "T : ";
52
        for (int i = 1; i <= n; ++i) {
53
            if (!inP[i]) cout << i << ' ';
54
        }
55
        cout << endl;
56
        cout << "d : ";
57
        for (int i = 1; i <= n; ++i) {
58
            if (d[i] == 0x3f3f3f3f) cout << "inf" << ' ';
59
            else cout << d[i] << ' ';
60
        }
61
        cout << endl << "*****************************" << endl;
62
    }
63
    return 0;
64
}

Floyd#

floyd.cpp

1
#include <iostream>
2
#include <cstring>
3
#include <iomanip>
4

5
using namespace std;
6

7
const int N = 10;
8
int D[N][N][N];
9

10
int main() {
11
    // 从 dat.txt 中读取数据
12
    freopen("dat.txt", "r", stdin);
13
    freopen("out_floyd.txt", "w", stdout);
14
    // 读取 & 预处理数据
15
    int n, m;
16
    cin >> n >> m;
17
    // 全部初始化成无穷大
18
    memset(D, 0x3f, sizeof(D));
19
    // 邻接矩阵主对角线初始化成 0
20
    for (int i = 1; i <= n; ++i) D[0][i][i] = 0;
21
    for (int i = 1; i <= m; ++i) {
22
        int x, y, z;
23
        cin >> x >> y >> z;
24
        D[0][x][y] = D[0][y][x] = z;
25
    }
26

27
    // 输出邻接矩阵
28
    cout << "A" << endl;
29
    for (int i = 1; i <= n; ++i) {
30
        for (int j = 1; j <= n; ++j) {
31
            if (D[0][i][j] == 0x3f3f3f3f) cout << " inf";
32
            else cout << setw(4) << D[0][i][j];
33
        }
34
        cout << endl;
35
    }
36
    cout << endl;
37

38
    // FLoyd 并输出 D_k
39
    for (int k = 1; k <= n; ++k) {
40
        cout << "D_" << k << endl;
41
        for (int i = 1; i <= n; ++i) {
42
            for (int j = 1; j <= n; ++j) {
43
                D[k][i][j] = min(D[k - 1][i][j], D[k - 1][i][k] + D[k - 1][k][j]);
44
                if (D[k][i][j] == 0x3f3f3f3f) cout << " inf";
45
                else cout << setw(4) << D[k][i][j];
46
            }
47
            cout << endl;
48
        }
49
        cout << endl;
50
    }
51
    return 0;
52
}

补充说明#

Dijkstra 可以用堆优化，优化后的 Dijkstra 可以应对结点数和边数都在十万级别的数据。
- 上面的代码没有写堆优化一方面是时间复杂度的瓶颈在输出过程上，另一方面是保证对初学者的可读性。
- 在同时带边权和点权的无向图上跑堆优化的 Dijkstra 详见我的另一篇 article，欢迎🎉🎉🎉。
Floyd 一般实现的时候不会开三维数组（可能是因为空间占用太大），不难发现如果不输出 D_k 的话第一维是多余的，直接在原邻接矩阵上操作不会影响结果， d[i][j] = min(d[i][j], d[i][k] + d[j][k]) 即可。

附录：代码输出#

out_dij.txt#

1
round 1
2
*****************************
3
P : 1
4
T : 2 3 4 5 6 7 8 9
5
d : 0 6 3 2 inf inf inf inf inf
6
*****************************
7
round 2
8
*****************************
9
P : 1 4
10
T : 2 3 5 6 7 8 9
11
d : 0 6 3 2 8 12 inf inf inf
12
*****************************
13
round 3
14
*****************************
15
P : 1 3 4
16
T : 2 5 6 7 8 9
17
d : 0 5 3 2 8 12 inf inf inf
18
*****************************
19
round 4
20
*****************************
21
P : 1 2 3 4
22
T : 5 6 7 8 9
23
d : 0 5 3 2 6 12 inf inf inf
24
*****************************
25
round 5
26
*****************************
27
P : 1 2 3 4 5
28
T : 6 7 8 9
29
d : 0 5 3 2 6 12 8 9 12
30
*****************************
31
round 6
32
*****************************
33
P : 1 2 3 4 5 7
34
T : 6 8 9
35
d : 0 5 3 2 6 12 8 9 11
36
*****************************
37
round 7
38
*****************************
39
P : 1 2 3 4 5 7 8
40
T : 6 9
41
d : 0 5 3 2 6 11 8 9 11
42
*****************************
43
round 8
44
*****************************
45
P : 1 2 3 4 5 6 7 8
46
T : 9
47
d : 0 5 3 2 6 11 8 9 11
48
*****************************
49
round 9
50
*****************************
51
P : 1 2 3 4 5 6 7 8 9
52
T :
53
d : 0 5 3 2 6 11 8 9 11
54
*****************************

out_floyd.txt#

1
A
2
   0   6   3   2 inf inf inf inf inf
3
   6   0   2 inf   1 inf inf inf inf
4
   3   2   0   2 inf inf inf inf inf
5
   2 inf   2   0   6  10 inf inf inf
6
 inf   1 inf   6   0  10   2   3   6
7
 inf inf inf  10  10   0 inf   2 inf
8
 inf inf inf inf   2 inf   0 inf   3
9
 inf inf inf inf   3   2 inf   0   4
10
 inf inf inf inf   6 inf   3   4   0
11

12
D_1
13
   0   6   3   2 inf inf inf inf inf
14
   6   0   2   8   1 inf inf inf inf
15
   3   2   0   2 inf inf inf inf inf
16
   2   8   2   0   6  10 inf inf inf
17
 inf   1 inf   6   0  10   2   3   6
18
 inf inf inf  10  10   0 inf   2 inf
19
 inf inf inf inf   2 inf   0 inf   3
20
 inf inf inf inf   3   2 inf   0   4
21
 inf inf inf inf   6 inf   3   4   0
22

23
D_2
24
   0   6   3   2   7 inf inf inf inf
25
   6   0   2   8   1 inf inf inf inf
26
   3   2   0   2   3 inf inf inf inf
27
   2   8   2   0   6  10 inf inf inf
28
   7   1   3   6   0  10   2   3   6
29
 inf inf inf  10  10   0 inf   2 inf
30
 inf inf inf inf   2 inf   0 inf   3
31
 inf inf inf inf   3   2 inf   0   4
32
 inf inf inf inf   6 inf   3   4   0
33

34
D_3
35
   0   5   3   2   6 inf inf inf inf
36
   5   0   2   4   1 inf inf inf inf
37
   3   2   0   2   3 inf inf inf inf
38
   2   4   2   0   5  10 inf inf inf
39
   6   1   3   5   0  10   2   3   6
40
 inf inf inf  10  10   0 inf   2 inf
41
 inf inf inf inf   2 inf   0 inf   3
42
 inf inf inf inf   3   2 inf   0   4
43
 inf inf inf inf   6 inf   3   4   0
44

45
D_4
46
   0   5   3   2   6  12 inf inf inf
47
   5   0   2   4   1  14 inf inf inf
48
   3   2   0   2   3  12 inf inf inf
49
   2   4   2   0   5  10 inf inf inf
50
   6   1   3   5   0  10   2   3   6
51
  12  14  12  10  10   0 inf   2 inf
52
 inf inf inf inf   2 inf   0 inf   3
53
 inf inf inf inf   3   2 inf   0   4
54
 inf inf inf inf   6 inf   3   4   0
55

56
D_5
57
   0   5   3   2   6  12   8   9  12
58
   5   0   2   4   1  11   3   4   7
59
   3   2   0   2   3  12   5   6   9
60
   2   4   2   0   5  10   7   8  11
61
   6   1   3   5   0  10   2   3   6
62
  12  11  12  10  10   0  12   2  16
63
   8   3   5   7   2  12   0   5   3
64
   9   4   6   8   3   2   5   0   4
65
  12   7   9  11   6  16   3   4   0
66

67
D_6
68
   0   5   3   2   6  12   8   9  12
69
   5   0   2   4   1  11   3   4   7
70
   3   2   0   2   3  12   5   6   9
71
   2   4   2   0   5  10   7   8  11
72
   6   1   3   5   0  10   2   3   6
73
  12  11  12  10  10   0  12   2  16
74
   8   3   5   7   2  12   0   5   3
75
   9   4   6   8   3   2   5   0   4
76
  12   7   9  11   6  16   3   4   0
77

78
D_7
79
   0   5   3   2   6  12   8   9  11
80
   5   0   2   4   1  11   3   4   6
81
   3   2   0   2   3  12   5   6   8
82
   2   4   2   0   5  10   7   8  10
83
   6   1   3   5   0  10   2   3   5
84
  12  11  12  10  10   0  12   2  15
85
   8   3   5   7   2  12   0   5   3
86
   9   4   6   8   3   2   5   0   4
87
  11   6   8  10   5  15   3   4   0
88

89
D_8
90
   0   5   3   2   6  11   8   9  11
91
   5   0   2   4   1   6   3   4   6
92
   3   2   0   2   3   8   5   6   8
93
   2   4   2   0   5  10   7   8  10
94
   6   1   3   5   0   5   2   3   5
95
  11   6   8  10   5   0   7   2   6
96
   8   3   5   7   2   7   0   5   3
97
   9   4   6   8   3   2   5   0   4
98
  11   6   8  10   5   6   3   4   0
99

100
D_9
101
   0   5   3   2   6  11   8   9  11
102
   5   0   2   4   1   6   3   4   6
103
   3   2   0   2   3   8   5   6   8
104
   2   4   2   0   5  10   7   8  10
105
   6   1   3   5   0   5   2   3   5
106
  11   6   8  10   5   0   7   2   6
107
   8   3   5   7   2   7   0   5   3
108
   9   4   6   8   3   2   5   0   4
109
  11   6   8  10   5   6   3   4   0

Star's Blog