20170831_floyd

//
//  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、输出路径使用递归，第一个节点打出，然后二分实现尾部打完，头部空缺。