Floyd_可以根据Dijikstra来写

#include<stdio.h>
#include<stdlib.h>
float weight_map[3][3] = {0,6,13,
                           10,0,4,
                           5,100000,0};
float ch_weight_map[3][3];
int path_map[3][3], ch_path_map[3][3];
void generate_path_map() {
    int i, j;
    for (i = 0; i < 3;i++) {
        for (j = 0; j < 3;j++) {
            if (weight_map[i][j] == 0 ) {
                path_map[i][j] = -1;
            }
            else if (weight_map[i][j] == (100000)) {
                path_map[i][j] = -1;
            }
            else {
                path_map[i][j] = i;
            }
        }
    }
}
void floyd() {
    int floow;
    for (floow = 0; floow < 3;floow++) {
        for (int i = 0; i < 3;i++) {
            for (int j = 0; j < 3; j++) {
                if (weight_map[i][floow] >0 && weight_map[floow][j]>0) {
                    if (weight_map[i][j] >= weight_map[i][floow] + weight_map[floow][j]) {
                        ch_weight_map[i][j] = weight_map[i][floow] + weight_map[floow][j];
                        ch_path_map[i][j] = path_map[floow][j];
                    }
                    else {
                        ch_weight_map[i][j] = weight_map[i][j];
                        ch_path_map[i][j] = path_map[i][j];
                    }
                }else if(weight_map[i][floow] == 0 || weight_map[floow][j] == 0) {
                    ch_weight_map[i][j] = weight_map[i][j];
                    ch_path_map[i][j] = path_map[i][j];
                }
            }
        }
        for (int i = 0; i < 3;i++) {
            for (int j = 0; j < 3;j++) {
                weight_map[i][j] = ch_weight_map[i][j];
                path_map[i][j] = ch_path_map[i][j];
            }
        }

    }
}
int main() {
    generate_path_map();
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            printf("%d ", path_map[i][j]);
        }
        printf("\n");
    }
    floyd();
    printf("\n");
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            printf("%.2f ", weight_map[i][j]);
        }
        printf("\n");
    }
    printf("\n");
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            printf("%d ", path_map[i][j]);
        }
        printf("\n");
    }
    return 0;
}

后续的path_map矩阵可以反推出任意两点之间的最短路径

原文地址：https://blog.csdn.net/2301_79216282/article/details/143028169

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！