赞
踩
计算图中每个顶点间的最短路径及路径长度
采用邻接矩阵表示图
代码如下:
- #include <stdio.h>
- #include <windows.h>
- #include <limits.h>
- //顶点数量
- #define MAX_VEX 6
- static int A[MAX_VEX][MAX_VEX] = {{0, 12, 3, -1, 9, 10},
- {12, 0, -1, 2, 6, -1},
- {3, -1, 0, 2, -1, 6},
- {-1, 2, 2, 0, 4, 7},
- {9, 6, -1, 4, 0, 4},
- {10, -1, 6, 7, 4, 0}};
- void Floyd(int (*A)[MAX_VEX], int (*path)[MAX_VEX]);
- void initpath(int (*A)[MAX_VEX], int (*path)[MAX_VEX]);
- void printPath(int (*path)[]);
- void printArr(int (*A)[MAX_VEX]);
- /*
- 初始化 path
- */
- void initpath(int (*A)[MAX_VEX], int (*path)[MAX_VEX])
- {
- for (int i = 0; i < MAX_VEX; i++)
- {
- for (int j = 0; j < MAX_VEX; j++)
- {
- //初始化,将A的所有元素设为-1 代表初始状态两节点间路径不经过中间节点
- (*(path + i))[j] = -1;
- }
- }
- printf("初始化 path后:\n");
- for (int i = 0; i < MAX_VEX; i++)
- {
- for (int j = 0; j < MAX_VEX; j++)
- {
- printf("[%d]", (*(path + i))[j]);
- }
- printf("\n");
- }
- }
- /*
- 佛洛依德算法,计算各个顶点到其他顶点的最短路径
- 图使用邻接矩阵表示法
- A[4][4] 图对应的邻接矩阵
- path[4][4] 记录路径
- */
- void Floyd(int (*A)[MAX_VEX], int (*path)[MAX_VEX])
- {
- initpath(A, path);
- //初始化完毕
- //核心循环处理每个节点
- for (int k = 0; k < MAX_VEX; k++)
- {
- for (int i = 0; i < MAX_VEX; i++)
- {
- int max = INT_MAX; //定义为无穷大
- for (int j = 0; j < MAX_VEX; j++)
- {
- //判断对于顶点k,是否有由以它为中转点从i到j的其它更短的路径 如果有,则更新矩阵path 与 A
- if (i != j && (*(A + i))[k] != -1 && (*(A + k))[j] != -1 && ((*(A + i))[j] > (*(A + i))[k] + (*(A + k))[j] || (*(A + i))[j] == -1))
- {
- //更新PATH与A
- (*(A + i))[j] = (*(A + i))[k] + (*(A + k))[j];
- (*(path + i))[j] = k;
- }
- }
- }
- printf("完成第%d遍扫描,将顶点%d作为中转点,打印A矩阵:\n", k + 1, k);
- printArr(A);
- printf("完成第%d遍扫描,将顶点%d作为中转点,打印path矩阵:\n", k + 1, k);
- printArr(path);
- }
- }
- /*
- 打印路径
- */
- void printPath(int (*path)[MAX_VEX])
- {
- //遍历path
- for (int i = 0; i < MAX_VEX; i++)
- {
- // posTempi = i;
- int path_trail[MAX_VEX][MAX_VEX + 1]; //用于存放遍历出的路径
- memset(path_trail, -1, sizeof(path_trail));
- for (int j = 0; j < MAX_VEX; j++)
- {
- //A的上三角区域 包括中轴
- if (j >= i)
- {
- int c = 1, k = j; //c 为 path_trail 第二维下标指针
- path_trail[k][MAX_VEX] = i; //路径起点
- path_trail[k][0] = k; //路径终点
- //在A的横向寻找路径
- while ((*(path + i))[j] != -1)
- {
- path_trail[k][c++] = (*(path + i))[j];
- j = (*(path + i))[j];
- }
- j = k;
- }else {
- //A的下三角区域
- int c = 1, k = i; //c 为 path_trail 第二维下标指针
- path_trail[j][MAX_VEX] = k; //路径起点
- path_trail[j][0] = j; //路径终点
- //在A的纵向寻找路径
- while ((*(path + i))[j] != -1)
- {
- path_trail[j][c++] = (*(path + i))[j];
- i = (*(path + i))[j];
- }
- i = k;
- }
- }
-
- //按顺序打印两顶点路径
- for (int i = 0; i < MAX_VEX; i++)
- {
- printf("顶点%d==>顶点%d最短路径:", path_trail[i][MAX_VEX], path_trail[i][0]);
- for (int j = MAX_VEX; j >= 0; j--)
- {
- if (path_trail[i][j] != -1)
- {
- printf("%d", path_trail[i][j]);
- if (j != 0)
- {
- printf("-->");
- }
- }
- }
- printf(" 路径长度为:%d\n",A[path_trail[i][MAX_VEX]][path_trail[i][0]]);
- }
- }
- }
- /*
- 打印矩阵
- */
- void printArr(int (*A)[MAX_VEX])
- {
- for (int i = 0; i < MAX_VEX; i++)
- {
- for (int j = 0; j < MAX_VEX; j++)
- {
- printf("[%2d]", (*(A + i))[j]);
- }
- printf("\n");
- }
- }
- int main(int argc, char const *argv[])
- {
-
- int path[MAX_VEX][MAX_VEX];
- Floyd(A, path);
- printPath(path);
- system("pause");
- }
打印输出:
初始化 path后:
[-1][-1][-1][-1][-1][-1]
[-1][-1][-1][-1][-1][-1]
[-1][-1][-1][-1][-1][-1]
[-1][-1][-1][-1][-1][-1]
[-1][-1][-1][-1][-1][-1]
[-1][-1][-1][-1][-1][-1]
完成第1遍扫描,将顶点0作为中转点,打印A矩阵:
[ 0][12][ 3][-1][ 9][10]
[12][ 0][15][ 2][ 6][22]
[ 3][15][ 0][ 2][12][ 6]
[-1][ 2][ 2][ 0][ 4][ 7]
[ 9][ 6][12][ 4][ 0][ 4]
[10][22][ 6][ 7][ 4][ 0]
完成第1遍扫描,将顶点0作为中转点,打印path矩阵:
[-1][-1][-1][-1][-1][-1]
[-1][-1][ 0][-1][-1][ 0]
[-1][ 0][-1][-1][ 0][-1]
[-1][-1][-1][-1][-1][-1]
[-1][-1][ 0][-1][-1][-1]
[-1][ 0][-1][-1][-1][-1]
完成第2遍扫描,将顶点1作为中转点,打印A矩阵:
[ 0][12][ 3][14][ 9][10]
[12][ 0][15][ 2][ 6][22]
[ 3][15][ 0][ 2][12][ 6]
[14][ 2][ 2][ 0][ 4][ 7]
[ 9][ 6][12][ 4][ 0][ 4]
[10][22][ 6][ 7][ 4][ 0]
完成第2遍扫描,将顶点1作为中转点,打印path矩阵:
[-1][-1][-1][ 1][-1][-1]
[-1][-1][ 0][-1][-1][ 0]
[-1][ 0][-1][-1][ 0][-1]
[ 1][-1][-1][-1][-1][-1]
[-1][-1][ 0][-1][-1][-1]
[-1][ 0][-1][-1][-1][-1]
完成第3遍扫描,将顶点2作为中转点,打印A矩阵:
[ 0][12][ 3][ 5][ 9][ 9]
[12][ 0][15][ 2][ 6][21]
[ 3][15][ 0][ 2][12][ 6]
[ 5][ 2][ 2][ 0][ 4][ 7]
[ 9][ 6][12][ 4][ 0][ 4]
[ 9][21][ 6][ 7][ 4][ 0]
完成第3遍扫描,将顶点2作为中转点,打印path矩阵:
[-1][-1][-1][ 2][-1][ 2]
[-1][-1][ 0][-1][-1][ 2]
[-1][ 0][-1][-1][ 0][-1]
[ 2][-1][-1][-1][-1][-1]
[-1][-1][ 0][-1][-1][-1]
[ 2][ 2][-1][-1][-1][-1]
完成第4遍扫描,将顶点3作为中转点,打印A矩阵:
[ 0][ 7][ 3][ 5][ 9][ 9]
[ 7][ 0][ 4][ 2][ 6][ 9]
[ 3][ 4][ 0][ 2][ 6][ 6]
[ 5][ 2][ 2][ 0][ 4][ 7]
[ 9][ 6][ 6][ 4][ 0][ 4]
[ 9][ 9][ 6][ 7][ 4][ 0]
完成第4遍扫描,将顶点3作为中转点,打印path矩阵:
[-1][ 3][-1][ 2][-1][ 2]
[ 3][-1][ 3][-1][-1][ 3]
[-1][ 3][-1][-1][ 3][-1]
[ 2][-1][-1][-1][-1][-1]
[-1][-1][ 3][-1][-1][-1]
[ 2][ 3][-1][-1][-1][-1]
完成第5遍扫描,将顶点4作为中转点,打印A矩阵:
[ 0][ 7][ 3][ 5][ 9][ 9]
[ 7][ 0][ 4][ 2][ 6][ 9]
[ 3][ 4][ 0][ 2][ 6][ 6]
[ 5][ 2][ 2][ 0][ 4][ 7]
[ 9][ 6][ 6][ 4][ 0][ 4]
[ 9][ 9][ 6][ 7][ 4][ 0]
完成第5遍扫描,将顶点4作为中转点,打印path矩阵:
[-1][ 3][-1][ 2][-1][ 2]
[ 3][-1][ 3][-1][-1][ 3]
[-1][ 3][-1][-1][ 3][-1]
[ 2][-1][-1][-1][-1][-1]
[-1][-1][ 3][-1][-1][-1]
[ 2][ 3][-1][-1][-1][-1]
完成第6遍扫描,将顶点5作为中转点,打印A矩阵:
[ 0][ 7][ 3][ 5][ 9][ 9]
[ 7][ 0][ 4][ 2][ 6][ 9]
[ 3][ 4][ 0][ 2][ 6][ 6]
[ 5][ 2][ 2][ 0][ 4][ 7]
[ 9][ 6][ 6][ 4][ 0][ 4]
[ 9][ 9][ 6][ 7][ 4][ 0]
完成第6遍扫描,将顶点5作为中转点,打印path矩阵:
[-1][ 3][-1][ 2][-1][ 2]
[ 3][-1][ 3][-1][-1][ 3]
[-1][ 3][-1][-1][ 3][-1]
[ 2][-1][-1][-1][-1][-1]
[-1][-1][ 3][-1][-1][-1]
[ 2][ 3][-1][-1][-1][-1]
顶点0==>顶点0最短路径:0-->0 路径长度为:0
顶点0==>顶点1最短路径:0-->2-->3-->1 路径长度为:7
顶点0==>顶点2最短路径:0-->2 路径长度为:3
顶点0==>顶点3最短路径:0-->2-->3 路径长度为:5
顶点0==>顶点4最短路径:0-->4 路径长度为:9
顶点0==>顶点5最短路径:0-->2-->5 路径长度为:9
顶点1==>顶点0最短路径:1-->2-->3-->0 路径长度为:7
顶点1==>顶点1最短路径:1-->1 路径长度为:0
顶点1==>顶点2最短路径:1-->3-->2 路径长度为:4
顶点1==>顶点3最短路径:1-->3 路径长度为:2
顶点1==>顶点4最短路径:1-->4 路径长度为:6
顶点1==>顶点5最短路径:1-->3-->5 路径长度为:9
顶点2==>顶点0最短路径:2-->0 路径长度为:3
顶点2==>顶点1最短路径:2-->3-->1 路径长度为:4
顶点2==>顶点2最短路径:2-->2 路径长度为:0
顶点2==>顶点3最短路径:2-->3 路径长度为:2
顶点2==>顶点4最短路径:2-->3-->4 路径长度为:6
顶点2==>顶点5最短路径:2-->5 路径长度为:6
顶点3==>顶点0最短路径:3-->2-->0 路径长度为:5
顶点3==>顶点1最短路径:3-->1 路径长度为:2
顶点3==>顶点2最短路径:3-->2 路径长度为:2
顶点3==>顶点3最短路径:3-->3 路径长度为:0
顶点3==>顶点4最短路径:3-->4 路径长度为:4
顶点3==>顶点5最短路径:3-->5 路径长度为:7
顶点4==>顶点0最短路径:4-->0 路径长度为:9
顶点4==>顶点1最短路径:4-->1 路径长度为:6
顶点4==>顶点2最短路径:4-->3-->2 路径长度为:6
顶点4==>顶点3最短路径:4-->3 路径长度为:4
顶点4==>顶点4最短路径:4-->4 路径长度为:0
顶点4==>顶点5最短路径:4-->5 路径长度为:4
顶点5==>顶点0最短路径:5-->2-->0 路径长度为:9
顶点5==>顶点1最短路径:5-->3-->1 路径长度为:9
顶点5==>顶点2最短路径:5-->2 路径长度为:6
顶点5==>顶点3最短路径:5-->3 路径长度为:7
顶点5==>顶点4最短路径:5-->4 路径长度为:4
顶点5==>顶点5最短路径:5-->5 路径长度为:0
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。