算法上机实验----单源+点对最短距离

发表于 | 分类于
Berman-Ford算法以及动态规划法求解

图的数据结构定义

单源最短路径的Berman-Ford算法是基于边的图算法，所以我使用二维的数组存储图的边数据。

点对最短路径是基于个点的，所以用邻接矩阵来存储图。

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
#include <stdio.h>
#define INF 100000
// int Graph1[5][5] = {
//     {INF,   6, INF,   7, INF},
//     {INF, INF,   5,   8,  -4},
//     {INF,  -2, INF, INF, INF},
//     {INF, INF,  -3, INF,   9},
//     {  2, INF,   7, INF, INF}
// };
char Graph1_V_name[5] = {'s', 't', 'x', 'y', 'z'};
int Graph1[10][3] = {
    {0, 1, 6},
    {0, 3, 7},
    {1, 2, 5},
    {1, 3, 8},
    {1, 4, -4},
    {2, 1, -2},
    {3, 2, -3},
    {3, 4, 9},
    {4, 0, 2},
    {4, 2, 7}
};
int Graph2[5][5] = {
//     1    2    3    4    5
    {  0,   3,   8, INF,  -4}, //1
    {INF,   0, INF,   1,   7}, //2
    {INF,   4,   0, INF, INF}, //3
    {  2, INF,  -5,   0, INF}, //4
    {INF, INF, INF,   6,   0}, //5
};

单源最短路径的实现

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
void solve_single_sourse(int v_n, int e_n) {
    int P[v_n];
    int D[v_n];
    for (int i = 0; i < v_n; i++) {
        P[i] = -1;
        D[i] = INF;
    }
    D[0] = 0;
    // 求解算法
    for (int k = 0; k < v_n-1; k++) {
        for (int i = 0; i < e_n; i++) {
            int u = Graph1[i][0];
            int v = Graph1[i][1];
            int w = Graph1[i][2];
            if (D[v] > D[u] + w) {
                D[v] = D[u] + w;
                P[v] = u;
            }
        }
    }
    // 回溯法求解路径
    char path[v_n];
    for (int k = 1; k < v_n; k++) {
        int l = 0;
        int v = k;
        printf("l:%2d ", D[k]);
        while(P[v] != -1) {
            path[l++] = Graph1_V_name[v];
            v = P[v];
        }
        printf("s");
        for (l--; l >=0; l--) {
            printf("->%c", path[l]);
        }
        printf("\n");
    }
}

运行结果

1
2
3
4
l: 2 s->y->x->t
l: 4 s->y->x
l: 7 s->y
l:-2 s->y->x->t->z

各点对最短路径

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
void solve_pair_distance(int n) {
    int L[n][n];
    int P[n][n];
    // 算法主体
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)  {
            L[i][j] = Graph2[i][j];
            P[i][j] = -1;
        }
    }
    for (int m = 1; m < n-1; m++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    if (L[i][j] > L[i][k] + Graph2[k][j]) {
                        L[i][j] = L[i][k] + Graph2[k][j];
                        P[i][j] = k; // 记录从i到j这条路径上的父节点
                    }
                }
            }
        }
    }
    // 输出各点对之间的最短距离
    for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                printf("%3d ", L[i][j]);
            }
            printf("\n");
        }
    // 根据P找出路径
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            printf("%d->", i+1);
            int buff[n], l = 0;
            int v = j;
            while(P[i][v] != -1) {
                buff[l++] = P[i][v];
                v = P[i][v];
            }
            for(l--; l>=0; l--) {
                printf("%d->", buff[l]+1);
            }
            printf("%d\n", j+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
  0   1  -3   2  -4 
  3   0  -4   1  -1 
  7   4   0   5   3 
  2  -1  -5   0  -2 
  8   5   1   6   0 
1->5->4->3->2
1->5->4->3
1->5->4
1->5
2->4->1
2->4->3
2->4
2->4->1->5
3->2->4->1
3->2
3->2->4
3->2->4->1->5
4->1
4->3->2
4->3
4->1->5
5->4->1
5->4->3->2
5->4->3
5->4

主函数

1
2
3
4
5
int main() {
    // solve_single_sourse(5, 10);
    solve_pair_distance(5);
    return 0;
}