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