网站后台这么做,网络设计与制作课程,网站开发需要哪些技术人员,广告设计内容弗洛伊德算法相比迪杰斯特拉相似的地方都是遍历邻接矩阵不断调整最短路径的信息#xff0c;并且两种算法面对多源最短路径的时间复杂度都是O(n^3)#xff0c;Floyd采用的是动态规划而Dijkstra是采用贪心的思想。在Floyd中我们将创建两个数组进行辅助#xff0c;一个path二维… 弗洛伊德算法相比迪杰斯特拉相似的地方都是遍历邻接矩阵不断调整最短路径的信息并且两种算法面对多源最短路径的时间复杂度都是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;
}无向权值图 运行结果
