迪杰斯特拉(dijkstra) + 弗洛伊德(floyd)

算法

/*
6 8
0 5 100
0 4 30
0 2 10
1 2 5
2 3 50
3 5 10
4 3 20
4 5 60
*/
#include <stdio.h>
#include <string.h>
const int MAXN = 100;
const int MAXV = 1e9 + 1;
int _min(int a, int b){
    return a > b ? b : a;
}
int G[MAXN][MAXN];
int N, M;
// 从start节点开始
// 图为G，邻接矩阵表示，节点个数为n
int* dijkstra(int start);
void Floyd();
int main(){
    scanf("%d %d", &N,&M);
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            G[i][j] = MAXV;
        }
    }
    int a, b, c;
    for(int i=0; i<M; i++){
        scanf("%d %d %d", &a, &b, &c);
        G[a][b] = c;
    }
    int* Lmin = dijkstra(0);
    for(int i=0; i<N; i++){
        int v = Lmin[i];
        if(v==MAXV){
            v = -1;
        }
        printf("%d\t", v);
    }
    printf("\n");
    Floyd();
}
int* dijkstra(int start){
    int* Lmin = new int[N];
    bool* visited = new bool[N];
    memset(visited, 0x00, sizeof(bool) * N);
    for(int i=0; i<N; i++){
        Lmin[i] = MAXV;
    }
    Lmin[start] = 0;
    int c_node = start;
    for(int i=0; i<N; i++){
        visited[c_node] = true;
        // 根据c_node更新没有访问过的Lmin的值
        for(int j=0; j<N; j++){
            if(visited[j] == false && G[c_node][j] < MAXV){
                Lmin[j] = _min(Lmin[j], Lmin[c_node] + G[c_node][j]);
            }
        }
        //
        for(int i=0; i<N; i++){
            int v = Lmin[i];
            if(v==MAXV){
                v = -1;
            }
            printf("%d\t", v);
        }
        printf("\n");
        for(int i=0; i<N; i++){
            printf("%d\t", visited[i]);
        }
        printf("\n");
        printf("----------------------------\n");
        //根据没有访问过的Lmin的最小值确定c_node
        int mmin = MAXV;
        for(int j=0; j<N; j++){
            if(visited[j] == false && Lmin[j] < mmin){
                c_node = j;
                mmin = Lmin[j];
            }
        }
    }
    return Lmin;
}
int D[MAXN][MAXN];
int P[MAXN][MAXN];
void Floyd(){
    // init D and P
    memcpy(D, G, sizeof(G));
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            P[i][j] = j;
        }
    }
    for(int k=0; k<N; k++){
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                int c = D[i][k] + D[k][j];
                if(c < D[i][j]){
                    D[i][j] = c;
                    P[i][j] = k;
                }
            }
        }
    }
    // Path
    int i=0, j=5, k;
    k = P[i][j];
    printf("%d", i);
    while(k != j){
        printf(" -> %d", k);
        k = P[k][j];
    }
    printf(" -> %d\n", j);
    printf("%d\n", D[i][j]);
}

6 8
0 5 100
0 4 30
0 2 10
1 2 5
2 3 50
3 5 10
4 3 20
4 5 60
0       -1      10      -1      30      100
1       0       0       0       0       0
----------------------------
0       -1      10      60      30      100
1       0       1       0       0       0
----------------------------
0       -1      10      50      30      90
1       0       1       0       1       0
----------------------------
0       -1      10      50      30      60
1       0       1       1       1       0
----------------------------
0       -1      10      50      30      60
1       0       1       1       1       1
----------------------------
0       -1      10      50      30      60
1       0       1       1       1       1
----------------------------
0       -1      10      50      30      60
0 -> 4 -> 3 -> 5
60

迪杰斯特拉是单源最短路，时间复杂度为$O(n^2)$，每次确定一个最小节点，如果需要输出单源最短路径，需要需要有一个Path[N]数组Path[i]保存最小节点为i时的中间节点

Fold算法求多源最短需要用一个D矩阵和P矩阵，D[i][j]为源为i目的为j的最小值，P[i][j]表示愿为i目的为j达到最小时的中间节点