佛洛依德
#include <stdio.h>#define NUM 5 //顶点数#define MV 65536 //最大值int P[NUM][NUM];//辅助数组,记录边的数组，不过是正序的，P【i】【j】从i到j的最短路径的第二个顶点，但不一定是j，只有初//始化的时候才一定是jint A[NUM][NUM];//记录每条路径的权值之和/*用邻接矩阵定义图，每个元素的数字代表相应边的权值，且注意邻接矩阵具有对称性*/int matrix[NUM][NUM] ={{ 0, 10, MV, 30, 100 },{ MV, 0, 50, MV, MV },{ MV, MV, 0, MV, 10 },{ MV, MV, 20, 0, 60 },{ MV, MV, MV, MV, 0 },};/*sv表示源点*/void Floyd(int sv){int i = 0;int j = 0;int k = 0;for (i = 0; i < NUM;i++){//初始化for (j = 0; j < NUM;j++){A[i][j] = matrix[i][j];P[i][j] = j;}}for (i = 0; i < NUM;i++){//i作为中转站，在最外层（关键点在dijkstra增加的）for (j = 0; j < NUM;j++){//目标是从j到kfor (k = 0; k < NUM;k++){if (A[j][i] + A[i][k] < A[j][k]){A[j][k] = A[j][i] + A[i][k];P[j][k] = P[j][i];//更新第二个顶点}}}}for (i = 0; i < NUM;i++){for (j = 0; j < NUM;j++){int p = -1;printf("%d->%d:%d\n",i,j,A[i][j]);printf("%d",i);p = i;do{p = P[p][j];printf("->%d",p);} while (p != j);printf("\n");}}}int main(){Floyd(0);system("PAUSE");return 0;}
如果觉得《最短路径佛洛依德》对你有帮助，请点赞、收藏，并留下你的观点哦！
