C语言-数据结构 弗洛伊德算法(Floyd)邻接矩阵存储

        弗洛伊德算法相比迪杰斯特拉相似的地方都是遍历邻接矩阵不断调整最短路径的信息，并且两种算法面对多源最短路径的时间复杂度都是O(n^3)，Floyd采用的是动态规划而Dijkstra是采用贪心的思想。在Floyd中我们将创建两个数组进行辅助，一个path二维数组用于存储路径信息，一个table二维数组用于记录更新各结点间的最短路径长度，table的初始化就是简单的把邻接矩阵的信息复制过来，整个算法都是在这个table表中不断更新，代码中第一层for循环是控制中转结点，另外两行就是遍历整个table二位数组，table[v][k]表示辅助列，table[k][w]表示辅助行，辅助行与辅助列由中转结点控制在整个table表的主对角线上运动，table[v][w]当前扫描的邻接结点信息，如果当前邻接结点的权值大于对应的（辅助行+辅助列的权值和），那么说明找到更短的路径需要进行更新权值，当前邻接结点信息改为（辅助行+辅助列的权值和），同时更新路径信息为中转结点（即前驱顶点），代码中path[v][k]存储了对应的中转结点信息，利用它更新当前邻接结点的前驱结点（对应的中转结点）信息，当循环结束整个图各顶点到达其他所有顶点的最短距离就计算完成了，最后我们打印table矩阵的上三角部分因为两个结点的表示可以用一个方向就行，例如A->F打印了就可以表示F->A，并不需求遍历完全部table矩阵信息，同时打印路径信息的第二个for循环有个+1操作是为了避免打印AA、BB这种自己到自己的路径，也就是不打印主对角线，path路径信息的存储也同样用到并查集的部分思想在上一篇博文提过，在代码中通过不断循环path路径能够找到它的前驱结点一步步把所有路径结点信息找到，相比迪杰斯特拉倒着找结点信息，这里我们可以之间通过path二维数组顺序查找到路径信息，也是非常巧妙的！

 我们将创建下面的无向权值图：

  邻接矩阵的绘制还是手动赋值上三角，并通过矩阵对称性生成整个邻接矩阵，其中最小生成树中需要用到权值，对应原本有边的地方之前我是用1表示，现在改成边对应的权值，之前的0表示没有边，现在改成99表示为无穷，其实应该换成更大的值以确保树的边权值都小于这个最大值，但为了方便对齐显示看邻接矩阵，就使用了比本图中各边长较大的99来表示最大值。

Floyd算法代码：

//存储所有顶点的路径信息
typedef int Patharc[MAXVEX][MAXVEX];
//最短路径表copy邻接矩阵，不断扫描更新各顶点相互间的最短距离
typedef int ShortestPathTable[MAXVEX][MAXVEX];
// Floyd算法实现
void Floyd(MGraph G, Patharc path, ShortestPathTable table) {int v, w, k;// 初始化表和路径矩阵for (v = 0; v < G.numNodes; v++) {for (w = 0; w < G.numNodes; w++) {table[v][w] = G.arc[v][w];  // 初始化最短路径表if (G.arc[v][w] < INFINITY) {path[v][w] = w;  // 有直接边时，路径是目标顶点}else {path[v][w] = -1; // 如果没有边，则设为 -1}}}// Floyd算法的核心计算for (k = 0; k < G.numNodes; k++) {  // 遍历每个顶点作为中间顶点for (v = 0; v < G.numNodes; v++) {  // 遍历起点for (w = 0; w < G.numNodes; w++) {  // 遍历终点// 如果通过顶点 k 的路径更短，则更新路径和最短路径表if (table[v][w] > table[v][k] + table[k][w]) {table[v][w] = table[v][k] + table[k][w];path[v][w] = path[v][k];}}}}// 打印各顶点间的最短路径printf("各顶点间最短路径如下：\n");for (v = 0; v < G.numNodes; v++) {for (w = v + 1; w < G.numNodes; w++) {  // 遍历每对顶点//Array数组存储顶点ABCDEFGHprintf("%c-%c weight:%d\n", Array[v], Array[w], table[v][w]);k = path[v][w];  // 从起点到终点的路径printf("path:%d", v);while (k != w) {  // 路径输出printf("->%d", k);k = path[k][w];}printf("->%d\n", w);}printf("\n");}
}

完整代码（包括邻接矩阵的创建、Floyd算法）

#include "stdio.h"    
#include "stdlib.h"   
#include "math.h"  
#include "time.h"// 禁用特定的警告
#pragma warning(disable:4996)// 定义一些常量和数据类型
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXVEX 8 /* 最大顶点数，用户定义 */
#define MAXEDGE 10 /* 最大边数，用户定义 */
#define GRAPH_INFINITY 99 /* 用0表示∞，表示不存在边 *//* 定义状态、顶点和边的类型 */
typedef int Status;  /* Status是函数的返回类型，如OK表示成功 */
typedef char VertexType; /* 顶点的类型，用字符表示 */
typedef int EdgeType; /* 边上的权值类型，用整数表示 */
typedef int Boolean; /* 布尔类型 */
// 定义顶点标签
char Array[] = "ABCDEFGHI";/* 图的邻接矩阵结构体 */
typedef struct
{VertexType vexs[MAXVEX]; /* 顶点表 */EdgeType arc[MAXVEX][MAXVEX]; /* 邻接矩阵，表示边的权值 */int numNodes, numEdges; /* 图中当前的顶点数和边数 */
} MGraph;//存储所有顶点的路径信息
typedef int Patharc[MAXVEX][MAXVEX];
//最短路径表copy邻接矩阵，不断扫描更新各顶点相互间的最短距离
typedef int ShortestPathTable[MAXVEX][MAXVEX];/* 创建一个无向网图的邻接矩阵表示 */
void CreateMGraph(MGraph* G)
{int i, j, k, w;// 初始化图的顶点数和边数G->numNodes = 8;G->numEdges = 10;// 初始化邻接矩阵和顶点表for (i = 0; i < G->numNodes; i++) {for (j = 0; j < G->numNodes; j++) {G->arc[i][j] = GRAPH_INFINITY; /* 初始化邻接矩阵为∞ */}G->vexs[i] = Array[i]; /* 初始化顶点表 */}G->arc[0][0] = GRAPH_INFINITY;G->arc[0][1] = 10;G->arc[0][2] = GRAPH_INFINITY;G->arc[0][3] = GRAPH_INFINITY;G->arc[0][4] = GRAPH_INFINITY;G->arc[0][5] = 11;G->arc[0][6] = GRAPH_INFINITY;G->arc[0][7] = GRAPH_INFINITY;G->arc[1][0] = GRAPH_INFINITY;G->arc[1][1] = GRAPH_INFINITY;G->arc[1][2] = 23;G->arc[1][3] = GRAPH_INFINITY;G->arc[1][4] = GRAPH_INFINITY;G->arc[1][5] = GRAPH_INFINITY;G->arc[1][6] = 12;G->arc[1][7] = GRAPH_INFINITY;G->arc[2][0] = GRAPH_INFINITY;G->arc[2][1] = GRAPH_INFINITY;G->arc[2][2] = GRAPH_INFINITY;G->arc[2][3] = 21;G->arc[2][4] = GRAPH_INFINITY;G->arc[2][5] = GRAPH_INFINITY;G->arc[2][6] = GRAPH_INFINITY;G->arc[2][7] = GRAPH_INFINITY;G->arc[3][0] = GRAPH_INFINITY;G->arc[3][1] = GRAPH_INFINITY;G->arc[3][2] = GRAPH_INFINITY;G->arc[3][3] = GRAPH_INFINITY;G->arc[3][4] = GRAPH_INFINITY;G->arc[3][5] = GRAPH_INFINITY;G->arc[3][6] = GRAPH_INFINITY;G->arc[3][7] = 11;G->arc[4][0] = GRAPH_INFINITY;G->arc[4][1] = GRAPH_INFINITY;G->arc[4][2] = GRAPH_INFINITY;G->arc[4][3] = GRAPH_INFINITY;G->arc[4][4] = GRAPH_INFINITY;G->arc[4][5] = 47;G->arc[4][6] = GRAPH_INFINITY;G->arc[4][7] = 80;G->arc[5][0] = GRAPH_INFINITY;G->arc[5][1] = GRAPH_INFINITY;G->arc[5][2] = GRAPH_INFINITY;G->arc[5][3] = GRAPH_INFINITY;G->arc[5][4] = GRAPH_INFINITY;G->arc[5][5] = GRAPH_INFINITY;G->arc[5][6] = 6;G->arc[5][7] = GRAPH_INFINITY;G->arc[6][0] = GRAPH_INFINITY;G->arc[6][1] = GRAPH_INFINITY;G->arc[6][2] = GRAPH_INFINITY;G->arc[6][3] = GRAPH_INFINITY;G->arc[6][4] = GRAPH_INFINITY;G->arc[6][5] = GRAPH_INFINITY;G->arc[6][6] = GRAPH_INFINITY;G->arc[6][7] = 8;G->arc[7][0] = GRAPH_INFINITY;G->arc[7][1] = GRAPH_INFINITY;G->arc[7][2] = GRAPH_INFINITY;G->arc[7][3] = GRAPH_INFINITY;G->arc[7][4] = GRAPH_INFINITY;G->arc[7][5] = GRAPH_INFINITY;G->arc[7][6] = GRAPH_INFINITY;G->arc[7][7] = GRAPH_INFINITY;// 由于是无向图，邻接矩阵是对称的，需要将其对称for (int i = 0; i < G->numNodes; i++) {for (int j = 0; j < G->numNodes; j++) {G->arc[j][i] = G->arc[i][j];}}// 打印邻接矩阵printf("邻接矩阵为：\n");printf("     ");for (int i = 0; i < G->numNodes; i++) {printf("%2d ", i); /* 打印列索引 */}printf("\n     ");for (int i = 0; i < G->numNodes; i++) {printf("%2c ", G->vexs[i]); /* 打印顶点标签 */}printf("\n");for (int i = 0; i < G->numNodes; i++) {printf("%2d", i); /* 打印行索引 */printf("%2c ", G->vexs[i]); /* 打印顶点标签 */for (int j = 0; j < G->numNodes; j++) {if (G->arc[i][j] != 99) {printf("\033[31m%02d \033[0m", G->arc[i][j]); /* 打印邻接矩阵中的权值 */}else {printf("%02d ", G->arc[i][j]); /* 打印邻接矩阵中的权值 */}}printf("\n");}
}// Floyd算法实现
void Floyd(MGraph G, Patharc path, ShortestPathTable table) {int v, w, k;// 初始化表和路径矩阵for (v = 0; v < G.numNodes; v++) {for (w = 0; w < G.numNodes; w++) {table[v][w] = G.arc[v][w];  // 初始化最短路径表if (G.arc[v][w] < INFINITY) {path[v][w] = w;  // 有直接边时，路径是目标顶点}else {path[v][w] = -1; // 如果没有边，则设为 -1}}}// Floyd算法的核心计算for (k = 0; k < G.numNodes; k++) {  // 遍历每个顶点作为中间顶点for (v = 0; v < G.numNodes; v++) {  // 遍历起点for (w = 0; w < G.numNodes; w++) {  // 遍历终点// 如果通过顶点 k 的路径更短，则更新路径和最短路径表if (table[v][w] > table[v][k] + table[k][w]) {table[v][w] = table[v][k] + table[k][w];path[v][w] = path[v][k];}}}}// 打印各顶点间的最短路径printf("\n各顶点间最短路径如下：\n");for (v = 0; v < G.numNodes; v++) {for (w = v + 1; w < G.numNodes; w++) {  // 遍历每对顶点//Array数组存储顶点ABCDEFGHprintf("%c-%c weight:%d\n", Array[v], Array[w], table[v][w]);k = path[v][w];  // 从起点到终点的路径printf("path:%d", v);while (k != w) {  // 路径输出printf("->%d", k);k = path[k][w];}printf("->%d\n", w);}printf("\n");}
}// 主函数
int main(void) {MGraph G;/* 创建图 */CreateMGraph(&G);  // 创建并初始化图 GPatharc path;ShortestPathTable table;Floyd(G, path, table);  // 计算最短路径return 0;
}

 无向权值图：

运行结果：