#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矩阵可以反推出任意两点之间的最短路径
本站资源均来自互联网,仅供研究学习,禁止违法使用和商用,产生法律纠纷本站概不负责!如果侵犯了您的权益请与我们联系!
转载请注明出处: 免费源码网-免费的源码资源网站 » Floyd_可以根据Dijikstra来写
发表评论 取消回复