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

server/2024/9/25 17:17:04/

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/server/116918.html

相关文章

android系统设计模式

Android官方架构组件介绍之LifeCycle,Android架构组件一共包括以下几个&#xff1a; LifeCycle &#xff1a; 与Activity和Fragment的生命周期有关LiveData &#xff1a;异步可订阅数据&#xff0c;也是生命周期感知ViewModel &#xff1a;视图数据持有模型&#xff0c;也是生…

算法-最少箭引爆气球(贪心+区间)

leetcode题目链接 这道题思路很简单&#xff0c;就是一个贪心&#xff0c;甚至都不需要合并区间。 开始需要对气球的结束坐标排序一下&#xff0c;然后定义一个end指向当前箭的最远位置。 然后开始遍历数组&#xff0c;如果出现区间起始位置比end大&#xff0c;则说明需要再…

鸿蒙NEXT生态应用核心技术理念:一次开发,多端部署

在万物互联时代&#xff0c;应用开发者也面临设备底座从手机单设备到全场景多设备的转变&#xff0c;通过全场景多设备作为全新的底座&#xff0c;为消费者带来万物互联时代更为高效、便捷的体验。 在万物智联时代重要机遇期&#xff0c;鸿蒙结合移动生态发展的趋势&#xff0…

GIS可视化软件:地理信息与遥感领域中的洞察之眼

在地理信息与遥感技术的广阔天地中&#xff0c;可视化软件如同一双洞察世界的明眸&#xff0c;将复杂的数据编织成生动、直观的画卷&#xff0c;为我们揭示地球的奥秘与城市的律动。本文将深入挖掘其技术核心、应用实例、未来趋势&#xff0c;探讨可视化软件如何为地理信息与遥…

系统架构师考试学习笔记第五篇——架构设计补充知识(23)知识产权

本章考点&#xff1a; 第23课时主要学习国家与行业标准、知识产权的内容。根据考试大纲,本课时知识点会涉及单项选择题,按以往全国计算机技术与软件专业技术资格(水平)考试的出题规律约占3分。本课时内容属于补充知识范畴,考题类型固定。本课时知识架构如图23.1所示。 一、知识…

vue原理分析(十四)研究new Vue()中的 initProvide

在Vue.prototype._init 中有一些init函数&#xff0c;今天我们来研究这些init函数 Vue.prototype._init function (options) {......{initProxy(vm);}......initLifecycle(vm);initEvents(vm);initRender(vm);callHook$1(vm, beforeCreate, undefined, false /* setContext *…

时序预测 | Matlab实现GA-CNN遗传算法优化卷积神经网络时间序列预测

时序预测 | Matlab实现GA-CNN遗传算法优化卷积神经网络时间序列预测 目录 时序预测 | Matlab实现GA-CNN遗传算法优化卷积神经网络时间序列预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 时序预测 | Matlab实现GA-CNN遗传算法优化卷积神经网络时间序列预测&#xff…

[OpenGL]使用OpenGL绘制三角形

一、简介 本文介绍了如何在linux/win(wsl2)环境下&#xff0c;使用GLFWGLAD实现绘制三角形。 本文内容基本根据LearnOpengGL-入门-你好&#xff0c;三角形整理完成&#xff0c;读者也可以参考LearnOpengGL-入门-你好&#xff0c;三角形自行学习如何使用OpenGL绘制三角形。 按…