美文网首页
20170831_floyd

20170831_floyd

作者: zhaohaoying | 来源:发表于2017-08-31 14:49 被阅读0次
    //
    //  main.cpp
    //  floyd
    //
    //  Created by Haoying Zhao on 17/8/31.
    //  Copyright © 2017年 Haoying Zhao. All rights reserved.
    //
    
    #include <iostream>
    using namespace std;
    #define N 6
    #define MAX 32767
    
    void print_path(int i, int j, int path[][N]) {
        if(path[i][j] == -1) {
            cout << "--->" << (char)('A'+j);
            return;
        }
        print_path(i, path[i][j],path);
        print_path(path[i][j], j,path);
    }
    
    int main(int argc, const char * argv[]) {
        int a[N][N];
        int path[N][N];
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++) {
                if(i != j) a[i][j] = MAX;
                else a[i][j] = 0;
                path[i][j] = -1;
            }
        a[0][1] = 6; a[1][0] = 6;a[0][2] = 3; a[2][0] = 3;
        a[1][2] = 2; a[2][1] = 2;a[1][3] = 5; a[3][1] = 5;
        a[2][3] = 3; a[3][2] = 3;a[2][4] = 4; a[4][2] = 4;
        a[3][5] = 3; a[5][3] = 3;a[3][4] = 2; a[4][3] = 2;
        a[4][5] = 5; a[5][4] = 5;
        for(int k = 0; k < N; k++)
            for(int i = 0; i < N; i++)
                for(int j = 0; j < N; j++) {
                    if(a[i][j] > a[i][k] + a[k][j]) {
                        a[i][j] = a[i][k] + a[k][j];
                        path[i][j] = k;
                    }
                }
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                cout << a[i][j] << " ";
            }
            cout << endl;
        }
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++) {
                if(i == j)
                    continue;
                cout << (char)('A'+i);
                print_path(i,j,path);
                cout << endl;
            }
        return 0;
    }
    

    输出:

    0 5 3 6 7 9 
    5 0 2 5 6 8 
    3 2 0 3 4 6 
    6 5 3 0 2 3 
    7 6 4 2 0 5 
    9 8 6 3 5 0 
    A--->C--->B
    A--->C
    A--->C--->D
    A--->C--->E
    A--->C--->D--->F
    B--->C--->A
    B--->C
    B--->D
    B--->C--->E
    B--->D--->F
    C--->A
    C--->B
    C--->D
    C--->E
    C--->D--->F
    D--->C--->A
    D--->B
    D--->C
    D--->E
    D--->F
    E--->C--->A
    E--->C--->B
    E--->C
    E--->D
    E--->F
    F--->D--->C--->A
    F--->D--->B
    F--->D--->C
    F--->D
    F--->E
    

    反思:
    1、二维数组传参时形参如果是二次指针则应先转换再使用,否则至少给出数组宽度。
    2、输出路径使用递归,第一个节点打出,然后二分实现尾部打完,头部空缺。

    相关文章

      网友评论

          本文标题:20170831_floyd

          本文链接:https://www.haomeiwen.com/subject/lmyqjxtx.html