数据结构应用实例(六)——最短路径

news/2024/9/18 10:55:14/ 标签: 数据结构

Content:

      • 一、题目描述
      • 二、算法思想
      • 三、代码实现
      • 四、小结

一、题目描述

  实现求最短路径的两种算法:Dijsktra 算法和 Floyd 算法;

二、算法思想

  1. Dijkstra算法
    求一个点到图中其余节点的最短路径;
    首先设置三个辅助数组:
      (1) f l a g , f l a g [ i ] = = 1 flag,flag[i]==1 flagflag[i]==1 表示已求得起点到节点 i i i 的最短路径;
      (2) p r e , p r e [ i ] pre,pre[i] prepre[i] 表示节点 i i i 的前驱;
      (3) d i s , d i s [ i ] dis,dis[i] disdis[i] 表示已经求得最短路径中的点到点 i i i 的最短路径长度;
    然后进行以下步骤:
    (1)、初始化(不妨设起点编号为0): f l a g [ 0 ] = 1 , f l a g [ i ] = 0 , i = 1 , 2 , ⋯ , n − 1 ; flag[0]=1, flag[i]=0, i=1,2,\cdots,n-1; flag[0]=1,flag[i]=0,i=1,2,,n1
    d i s [ 0 ] = 0 , d i s [ i ] = G → A [ 0 ] [ i ] , i = 1 , 2 , ⋯ , n − 1 ; dis[0]=0, dis[i]=G\to A[0][i], i=1,2,\cdots,n-1; dis[0]=0,dis[i]=GA[0][i],i=1,2,,n1
    p r e [ 0 ] = 0 , p r e [ i ] = 0 pre[0]=0, pre[i]=0 pre[0]=0,pre[i]=0 如果 d i s [ i ] < ∞ , p r e [ i ] = − 1 dis[i]<\infty,pre[i]=-1 dis[i]<pre[i]=1 如果 d i s [ i ] = = ∞ , i = 1 , 2 , ⋯ , n − 1 dis[i]==\infty,i=1,2,\cdots,n-1 dis[i]==i=1,2,,n1
    (2)、选择 d i s [ j ] = M i n { d i s [ i ] ∣ f l a g [ i ] = = 0 } dis[j]=Min\lbrace dis[i] | flag[i]==0 \rbrace dis[j]=Min{dis[i]flag[i]==0},如果 d i s [ j ] < ∞ dis[j]<\infty dis[j]<,使 f l a g [ j ] = 1 flag[j]=1 flag[j]=1
    (3)、更新 d i s [ i ] dis[i] dis[i] p r e [ i ] pre[i] pre[i] i i i 号节点为 j j j 号节点的直接后继且 f l a g [ i ] = = 0 flag[i]==0 flag[i]==0,如果 d i s [ i ] > d i s [ j ] + G → A [ j ] [ i ] dis[i]>dis[j]+G\to A[j][i] dis[i]>dis[j]+GA[j][i],令 d i s [ i ] = d i s [ j ] + G → A [ j ] [ i ] , p r e [ i ] = j dis[i]=dis[j]+G\to A[j][i], pre[i]=j dis[i]=dis[j]+GA[j][i],pre[i]=j,程序中使用邻接表进行处理;
    (4)、重复步骤(2)、(3),直到 f l a g [ i ] = 1 , i = 0 , 1 , ⋯ , n − 1 flag[i]=1,i=0,1,\cdots,n-1 flag[i]=1,i=0,1,,n1 或者选择的节点 j j j 满足 d i s [ j ] = = ∞ dis[j]==\infty dis[j]==
    经过上述过程即可求得起点到可到达节点的最短路径;

  2. Floyd 算法
    求图中任意两点间的最短路径;
    以求顶点 v i v_i vi v j v_j vj 的最短路径为例, G → A [ i ] [ j ] G\to A[i][j] GA[i][j] 不一定恰好是最短路径,也许经过其他节点中转后得到的路径长度更短,因此需要进行 n 次试探;
      第 k 次试探,中间节点的编号均不超过 k-1,从第 k 次到第 k+1 次的做法,添加节点 k,如果 v [ 1 , ⋯ , k ] v[1,\cdots,k] v[1,,k] v [ k , ⋯ , j ] v[k,\cdots,j] v[k,,j] (中间节点的编号均不超过 k-1) 拼接成的路径 v [ i , ⋯ , k , ⋯ , j ] v[i,\cdots,k,\cdots,j] v[i,,k,,j] v [ i , ⋯ , j ] v[i,\cdots,j] v[i,,j] (中间节点的编号均不超过 k-1) 长度更短,则更新 v i v_i vi v j v_j vj 的路径;经过 n 次试探之后,得到 v [ i , ⋯ , j ] v[i,\cdots,j] v[i,,j] (中间节点的编号均不超过 n-1),此时的路径即为 v i v_i vi v j v_j vj 的最短路径;
      编程时采用两个辅助数组 p a t h path path D D D p a t h [ i ] [ j ] path[i][j] path[i][j] 记录 v i v_i vi v j v_j vj 的路径上的最后一个中转点,初始值为 i i i D [ i ] [ j ] D[i][j] D[i][j] 记录 v i v_i vi v j v_j vj 的路径长度, D D D 初始值为 G → A G\to A GA;进行 n 次试探,也就是对 p a t h path path D D D 进行了 n 次更新,最终得到想要结果;

三、代码实现

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxx 99999
#pragma warning(disable:4996)typedef struct arc//弧
{	int index;//指向节点编号int weight;//边的权值struct arc *next;
}AR;typedef struct MyGraph//图(包含邻接矩阵和邻接表)
{int type;//0表示无向图,1表示有向图int arcnum,vexnum;//边的个数、顶点个数char **vexname;//存放顶点名称的二维数组	AR *N;//表头数组int **A;//邻接矩阵
}GH;int findvex(char *s,GH *G);//找到图G中名称为s的节点编号,并将其返回
void createGraph(GH *G);//创建图G
void showGraph(GH *G);//以邻接表的形式显示图G
void Dijkstra(GH *G,char *start);//Dijkstra算法求图G中点start到其余节点的最短路径
void Floyd(GH *G);//Floyd算法求图G中任意两点间的最短路径
void showPath(GH *G,int **path,int i,int j);//递归输出Floyd算法中i号节点到j号节点的最短路径,path存放最后一个中转点int main(void)
{char start[20];GH *G=(GH *)malloc(sizeof(GH));//创建图createGraph(G);printf("图的邻接表形式:\n");showGraph(G);//Dijkstra算法printf("\n=========================Dijkstra算法===============================\n");printf("请输入起点名称(#表结束):\n");scanf("%s",start);while (strcmp(start, "#")){Dijkstra(G,start);printf("\n请输入起点名称(#表结束):\n");scanf("%s",start);}system("pause");printf("\n\n===========================Floyd算法===============================\n");//Floyd算法Floyd(G);printf("\n");free(G);return 0;
}int findvex(char *s,GH *G)//找到图G中名称为s的节点编号,并将其返回
{for(int i=0;i<G->vexnum;i++){if(strcmp(s,G->vexname[i])==0)//找到匹配节点return i;}printf("该点不存在\n");exit(-1);
}void createGraph(GH *G)//创建图G
{int i,j,n,edge;char filename[]="graph1.txt";//存放图的数据文件char str[10],str1[10];FILE *fp;AR *p;fp=fopen(filename,"r");if(!fp){printf("打开文件失败!\n");exit(-1);}fscanf(fp,"%d",&G->type);//读取图的类型G->arcnum=0;fscanf(fp,"%d",&n);//读取结点数量G->vexnum=n;//为动态数组分配空间G->vexname=(char **)malloc(n*sizeof(char *));G->N=(AR *)malloc(n*sizeof(AR));G->A=(int **)malloc(n*sizeof(int *));//对头结点数组和邻接矩阵初始化for (i = 0; i < n; i++){G->N[i].next = NULL;G->A[i] = (int *)malloc(n*sizeof(int));for (j = 0; j < n; j++)G->A[i][j]=maxx;}//读取顶点名称for(i=0;i<n;i++){fscanf(fp,"%s",str);G->vexname[i]=(char *)malloc(strlen(str)*sizeof(char));strcpy(G->vexname[i],str);}//读取边while(!feof(fp)){fscanf(fp,"%s",str);fscanf(fp,"%s",str1);fscanf(fp,"%d",&edge);i=findvex(str,G);j=findvex(str1,G);//邻接表p=(AR *)malloc(sizeof(AR));p->index=j;p->weight=edge;p->next=G->N[i].next;G->N[i].next=p;//邻接矩阵G->A[i][j]=edge;G->arcnum++;//边的个数增加if(G->type==0)//如果是无向图{//邻接表p=(AR *)malloc(sizeof(AR));p->index=i;p->weight=edge;p->next=G->N[j].next;G->N[j].next=p;//邻接矩阵G->A[j][i]=edge;}}fclose(fp);
}void showGraph(GH *G)//以邻接表的形式显示图G
{int i;AR *p;//用于遍历for (i = 0; i < G->vexnum; i++){printf("%s",G->vexname[i]);p=G->N[i].next;while (p){if (G->type == 1)printf("-->");else//无向图没有箭头printf("--");printf("%s(%d)",G->vexname[p->index],p->weight);p=p->next;}printf("\n");}printf("\n");
}void Dijkstra(GH *G,char *start)//Dijkstra算法求图G中点start到其余节点的最短路径
{int i,n,begin,next;int min;int *flag,*dis,*pre;int *t,top,p;AR *q;begin=findvex(start,G);//起点编号n=G->vexnum;flag=(int *)malloc(n*sizeof(int));//指示是否找到最短路径dis=(int *)malloc(n*sizeof(int));//已求得最短路径的点到该点的最短路径的长度pre=(int *)malloc(n*sizeof(int));//前驱t=(int *)malloc(n*sizeof(int));//建立栈,存储路径//数组初始化for (i = 0; i < n; i++){flag[i]=0;dis[i]=G->A[begin][i];if (dis[i] < maxx)pre[i]=begin;elsepre[i]=-1;}flag[begin]=1;dis[begin]=0;pre[begin]=-1;//在未找到最短路径的点中挑选路径最短的点min=maxx;for (i = 0; i < n; i++){if (flag[i] == 0 && dis[i] < min){min=dis[i];next=i;}}while(min < maxx)//找到之后,如果min<maxx,说明有新的点的flag将会被设为1{flag[next]=1;q=G->N[next].next;while (q)//更新next的未找到最短路径的直接后继的最短路径长度和前驱{if (flag[q->index] == 0 && dis[q->index] > dis[next] + (q->weight)){dis[q->index]= dis[next] + (q->weight);pre[q->index]=next;}q=q->next;}		//继续寻找最近点min=maxx;for (i = 0; i < n; i++){if (flag[i] == 0 && dis[i] < min){min=dis[i];next=i;}}}//寻找结束,结果输出printf("\n起点到各个顶点的最短路径:\n\n");for (i = 0; i < n; i++){if(i==begin)continue;printf("%s--%s:",G->vexname[begin],G->vexname[i]);if (pre[i] == -1)printf("从起点出发无法到达该点\n");else{top = -1;p = i;  while (p != begin)//将前驱依次放入栈中{top++;t[top] = p;p = pre[p];}printf("%s",G->vexname[begin]);while (top >= 0)//利用栈实现路径的正向输出{p=t[top];top--;printf("-->%s",G->vexname[p]);}printf("  最短路径长度为:%d\n",dis[i]);}printf("\n");}free(flag);free(dis);free(pre);free(t);
}void Floyd(GH *G)//Floyd算法求图G中任意两点间的最短路径
{int i,j,k,n;int **path,**D;n=G->vexnum;//节点个数path=(int **)malloc(n*sizeof(int*));//两点间最短路径上的最后一个中转点D=(int **)malloc(n*sizeof(int*));//两点间最短路径长度//初始化for (i = 0; i < n; i++){path[i]=(int *)malloc(n*sizeof(int));D[i]=(int *)malloc(n*sizeof(int));for (j = 0; j < n; j++){path[i][j]=i;D[i][j]=G->A[i][j];}}for (k = 0; k < n; k++)//中转点层为最外层for (i = 0; i < n; i++)for (j = 0; j < n; j++)if (D[i][j] > D[i][k] + D[k][j])//更新路径长度和中转点{D[i][j]= D[i][k] + D[k][j];path[i][j]=k;}//显示路径printf("\n两点间的最短路径为:\n");for (i = 0; i < n; i++){for (j = 0; j < n; j++){if(j==i)continue;printf("\n%s--%s:",G->vexname[i],G->vexname[j]);if (D[i][j] == maxx)printf("这两点之间没有路径\n");else{printf("%s",G->vexname[i]);showPath(G, path, i, j);printf("%s",G->vexname[j]);printf("  最短路径长度为:%d\n", D[i][j]);}}}free(path);free(D);
}void showPath(GH *G,int **path,int i,int j)//递归输出Floyd算法中i号节点到j号节点的最短路径,path存放最后一个中转点
{   //假定两点之间存在路径int k=path[i][j];//基准情况:没有中转点if(k==i)printf("-->");else//非基准情况{showPath(G,path,i,k);printf("%s",G->vexname[k]);showPath(G,path,k,j);}
}

四、小结

1、 采用递归的方式输出路径,为得到正确结果,将起点和终点放在递归函数外进行输出;
2、 迪杰斯特拉算法中,选择新加入的节点 j j j 时,如果 d i s [ j ] = = ∞ dis[j]==\infty dis[j]==,算法也会结束;


http://www.ppmy.cn/news/1525543.html

相关文章

【Android笔记】Android Studio打包 提示Invalid keystore format

前言 Android项目通过Android Studio生产签名文件进行打包。提示 com.android.ide.common.signing.KeytoolException: Failed to read key hocsdn from store "/Users/ho/TestProject/app/ho_developer.jks": Invalid keystore format 不合法的签名文件格式&#…

【Linux】ldd常见问题

ldd常见问题排查 ldd命令 背景: 今日链接到客户现场,发现客户环境异常,查看日志报出.so文件无法找到 思路: 怀疑so文件丢失或者权限异常。 可以使用ldd命令来查看问题 ldd /usr/bin/xxxxx会显示出相关的so文件,例: # ldd /usr/bin/lightdm-deepin-greeterlinux-v…

Navigation之使用Safe Args传递数据(二)

系列文章目录 Navigation的简单使用(一&#xff09; 一、Safe Args传递数据 1.引入库 1.将 Safe Args 添加到您的项目&#xff0c;请在顶层 build.gradle 文件中包含以下 classpath&#xff1a; buildscript {repositories {google()}dependencies {def nav_version "…

C++设计模式——Iterator迭代器模式

一&#xff0c;迭代器模式的定义 迭代器模式是一种行为型设计模式&#xff0c;它使得遍历一个容器对象中的元素变得更加简单。 迭代器模式将遍历操作从容器对象&#xff08;如集合、列表&#xff09;中分离出来&#xff0c;它通过迭代器对象来遍历容器对象中的元素&#xff0…

基于SpringBoot的求职招聘管理系统

作者&#xff1a;计算机学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI等&#xff0c;“文末源码”。 专栏推荐&#xff1a;前后端分离项目源码、SpringBoot项目源码、SSM项目源码 系统展示 【2025最新】基于JavaSpringBootVueMySQL的求职招聘管理系统…

Java 类和对象-小结(重要)

1&#xff0e;类和对象&#xff1a;类是一个模板&#xff0c;抽象的&#xff0c;对象是一个具体的实例。 2&#xff0e;方法&#xff1a;定义和调用 3&#xff0e;对象的引用&#xff1a; &#xff08;1&#xff09;除了八大基本类型之外&#xff0c;都是引用类型。 &#…

Ubuntu20-xrdp与Windows-mstsc远程桌面连接

ubuntu端 sudo adduser yu //输入密码和确认密码&#xff0c;后面一路回车&#xff0c;新建用户yu&#xff0c;确保用户没有被登录 sudo apt install xrdp //安装xrdp sudo systemctl status xrdp //查看xrdp服务状态 sudo adduser xrdp ssl-cert //将用户 xrdp 添加到 ss…

Hive和Hbase的区别

Hive 和 HBase 都是 Hadoop 生态系统中的重要组件&#xff0c;它们都能处理大规模数据&#xff0c;但各自有不同的适用场景和设计理念。以下是两者的主要区别&#xff1a; 1. 数据模型 Hive&#xff1a;Hive 类似于传统的关系型数据库 (RDBMS)&#xff0c;以表格形式存储数据…

动态ip切换过快,会引起我的账号下次登录异常吗

在网络世界中&#xff0c;动态IP地址的使用为用户提供了灵活性和隐私保护。然而&#xff0c;频繁且快速地切换IP地址可能会引起一些安全问题&#xff0c;尤其是在涉及到账号登录时。本文将探讨动态IP切换过快是否会导致账号登录异常&#xff0c;以及如何平衡IP切换的速度与账号…

k8s--pod控制器--1

Pod控制器介绍 Pod是kubernetes的最小管理单元&#xff0c;在kubernetes中&#xff0c;按照pod的创建方式可以将其分为两类&#xff1a; 自主式pod&#xff1a;kubernetes直接创建出来的Pod&#xff0c;这种pod删除后就没有了&#xff0c;也不会重建 控制器创建的pod&#xf…

前端工程化2:从0到1的eslint插件开发教程

从0-1的eslint插件开发教程 开发eslint插件目的&#xff1a;根据项目需要&#xff0c;自定义满足项目特殊需要的校验规则是 参考eslint官方文档展开阐述 插件开发 自定义规则 单元测试 下面开始通过一个示例demo来介绍插件整个开发流程 代码中出现的方法及变量的详细解释与…

NoSQL之Redis配置与优化(2)

一、Redis高可用 Redis 高可用性 1. 持久化 目的&#xff1a;避免数据因进程退出等原因而丢失&#xff0c;通过将数据从内存保存到硬盘&#xff0c;实现数据备份。主要方式&#xff1a; RDB 持久化&#xff1a;将内存中的数据生成快照保存到磁盘。适合定期备份数据&#xff…

深入理解 Vue 3 中的易混淆概念:全面解析及最佳实践20240909

深入理解 Vue 3 中的易混淆概念&#xff1a;全面解析及最佳实践 引言 Vue 3 的发布为前端开发带来了全新的组合式 API&#xff0c;这一革新使得代码的可维护性和复用性大大提升。然而&#xff0c;随着这些新特性的引入&#xff0c;也带来了一些容易混淆的概念。无论你是初学者…

微积分复习笔记 Calculus Volume 1 - 1.5 Exponential and Logarithmic Functions

1.5 Exponential and Logarithmic Functions - Calculus Volume 1 | OpenStax

package.json中~1.0.0和^1.0.0有什么区别

~会匹配最近的小版本依赖包&#xff0c;比如~1.2.3会匹配所有1.2.0 ~ 1.2.9 版本&#xff0c;但是不包括1.3.0&#xff0c;也就是1.2.x ^会匹配最新的大版本依赖包&#xff0c;比如^1.2.3会匹配所有1.x.x的包&#xff0c;包括1.3.0&#xff0c;但是不包括2.0.0 注意 如果前面…

数据库运维实操优质文章文档分享(含Oracle、MySQL等) | 2024年8月刊

本文为大家整理了墨天轮数据社区2024年8月发布的优质技术文章/文档&#xff0c;主题涵盖Oracle、MySQL、PostgreSQL等主流数据库系统以及国产数据库的技术实操&#xff0c;从基础的安装配置到复杂的故障排查&#xff0c;再到性能优化的实用技巧及常用脚本等&#xff0c;分享给大…

并行计算范式的时空辩证

来读一篇早年(September 27, 2017)的文章&#xff1a;The network era requires new models, with interactions instead of algorithms. 这篇文章迟到了很久&#xff0c;我在十多年前提到过一个相关的时空辩证&#xff1a; CPU 在时间序顺序执行指令流&#xff0c;基于图灵机…

职业技能大赛背景下的移动互联网应用软件开发(Android)实训室建设方案

一、建设背景 随着科技的持续进步&#xff0c;移动设备已成为人们日常生活中不可或缺的一部分。据相关数据&#xff0c;移动互联网的使用率在近年来显著上升。在这样的背景下&#xff0c;移动互联技术不仅推动了科技的发展&#xff0c;也渗透到了智能家居、车联网、工业自动化…

blender云渲染来了,blender云渲染教程!

朋友们&#xff0c;成都渲染101农场blender云渲染上线了&#xff0c;继3DMAX/C4D/maya/UE5云渲染上线后&#xff0c;又上线了blender云渲染&#xff0c;今天&#xff0c;成都渲染101渲染农场用四步教会您blender云渲染&#xff01; 第一步&#xff0c;云渲码6666注册个渲染101…

CSS Clip-Path:重塑元素边界的艺术

在Web设计中&#xff0c;创造独特而富有吸引力的视觉效果一直是设计师和开发者们追求的目标。CSS的clip-path属性为此提供了一个强大的工具&#xff0c;它允许我们定义元素的可见区域&#xff0c;从而以非矩形的方式裁剪图像或容器。这一特性不仅限于简单的形状裁剪&#xff0c…