当前位置： 首页 > news >正文

深圳做二类学分的网站人跟狗做网站

news 2025/9/17 11:35:53
深圳做二类学分的网站,人跟狗做网站,湘潭网络推广,淄博企业建网站弗洛伊德算法相比迪杰斯特拉相似的地方都是遍历邻接矩阵不断调整最短路径的信息，并且两种算法面对多源最短路径的时间复杂度都是O(n^3)，Floyd采用的是动态规划而Dijkstra是采用贪心的思想。在Floyd中我们将创建两个数组进行辅助，一个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二维数组顺序查找到路径信息，也是非常巧妙的！

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

84ef03cba4ba478383b338ae5884012a.png

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

9eefaa5c866742cbb239f5f9de2aff7d.png

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;
}

 无向权值图：

84ef03cba4ba478383b338ae5884012a.png

运行结果：

http://www.yayakq.cn/news/578574/

相关文章：

  • 我学的 网站开发 能进华为公司么室内效果图用什么软件做最好
  • 网站域名怎么转玉溪seo
  • 如何将优酷视频放到自己的网站网页模板下载html格式
  • 周易八字排盘系统网站建设卡盟网站怎么做图片
  • 北京大学廉政建设研究中心网站网站 什么语言开发的
  • 网站可以做的线下活动新增病例最新消息
  • html免费素材如何优化网站首页代码
  • 网站开发php技术群晖wordpress外网无法仿问
  • 重庆大渡口建设网站网站提交自动秒收录
  • 从零开始做网站内容运营网站备案背景幕布是什么
  • 网站开发项目流程书网站建设需求确认书
  • 乐达网站建设公司php网站后台地址
  • 深圳公司网站建设北京高端购物商场
  • 网站域名申请之后如何做网站毕节市交通建设集团网站
  • 推广网站怎么建设wordpress网站下方
  • 如何做微信官方网站网站建设现在好做吗
  • 长春企业公司网站建设杭州网站推广营销服务
  • 太原网站建设团队网页制作与网站建设实战大全 视频
  • 专业网站建设大型公司网站建设网站营销网站托管一体化
  • 苏州城乡建设网站小皮怎么创建网站
  • 南京品牌网站建设辽宁网站建设哪里好
  • 婚纱网站怎么做seo绍兴免费做网站
  • 和平网站建设优化seo河南网站建设哪个公司做得好
  • flash网站链接怎么做safari浏览器
  • 北京做电子系统网站的公司开网站建设需要办什么手续
  • 什么网站免费做推广wordpress图片上传失败
  • 帝国后台网站如何设置自动刷新首网站换域名了怎么办
  • 贵阳商城网站建设上饶网站建设srsem
  • 做装饰公司网站郑州百度搜索优化
  • 深圳龙华的学校网站建设wordpress 标签云链接