南邮数据结构实验3.5:飞机换乘最短距离(Dijkstra单源最短路径)

本文主要是介绍南邮数据结构实验3.5:飞机换乘最短距离(Dijkstra单源最短路径),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:编写程序,实现智能交通中的最佳路径选择问题:设有n个地点,编号为0~n-1,m条路径的起点、终点和代价由用户输入提供,采用实验3.1所示邻接矩阵为存储结构,寻找最佳路径方案(如花费时间最少、路径长度最短、交通费用最小等,任选其一即可)。

部分代码:

选出最小的d[i]:

//选出最小的d[i],i ∈ V-S
int Choose(int d[],int n,int s[]){  //对教材进行了一点改动,形式参数设置为数组而不是指针,参考了陈惠南老师的《数据结构——C语言描述》int i,minpos;ElemType min;min = INFTY;minpos = -1;for(i = 0;i < n;i ++){         //这里i初值改为0if(d[i] <= min && !s[i]){  //<改为<=min = d[i];minpos = i;}}return minpos;                //返回下标位置
}

Dijkstra算法:

//Dijkstra算法
Status Dijkstra(mGraph g,int v,int d[],int path[]){  //对教材进行了一点改动,形式参数设置为数组而不是指针,参考了陈惠南老师的《数据结构——C语言描述》int i,k,w,distance = 0;       //增加了一个distance记录最短距离之和int *s;if(v < 0||v > g.n-1){return ERROR;}s = (int*)malloc(g.n*sizeof(int));for(i = 0;i < g.n;i ++){      //初始化s[i] = 0;                 //表示顶点i是否在s中d[i] = g.a[v][i];         //v到i的距离if(i != v && d[i] < INFTY){path[i] = v;          //标识指向i的源点v}else path[i] = -1;}s[v] = 1;                     //顶点v为源点,将原点v加入集合Sprintf("%d ",v);              //输出源点0d[v] = 0;for(i = 1;i <= g.n-1;i ++){   //产生n-1条最短路径,<改为<=k = Choose(d,g.n,s);      //求当前路径最短者ks[k] = 1;                 //将k加入集合S中printf("%d ",k);for(w = 0;w < g.n;w ++){  //更新d和pathif(!s[w] && d[k]+g.a[k][w] < d[w]){d[w] = d[k] + g.a[k][w];distance = d[w];  //计算min距离path[w] = k;}}}printf("\nThe shortest distance:%d ",distance);return OK;
}

完整程序:

#include<stdio.h>
#include<stdlib.h>
#include <windows.h>
#define ERROR 0
#define OK 1
#define Overflow 2     //表示上溢
#define Underflow 3    //表示下溢
#define NotPresent 4   //表示元素不存在
#define Duplicate 5    //表示有重复元素
#define INFTY 32767    //表示极大值正无穷
typedef int ElemType;
typedef int Status;//邻接矩阵的结构体定义
typedef struct{ElemType **a;     //邻接矩阵int n;            //顶点数int e;            //边数ElemType noEdge;  //两顶点间无边时的值
}mGraph;//邻接矩阵的初始化
Status Init(mGraph *mg,int nSize,ElemType noEdgeValue){int i,j;mg->n = nSize;               //初始化顶点数mg->e = 0;                   //初始化时没有边mg->noEdge = noEdgeValue;    //初始化没有边时的取值mg->a = (ElemType**)malloc(nSize*sizeof(ElemType *));  //生成长度为n的一维指针数组if(!mg->a) return ERROR;for(i = 0;i < mg->n;i ++){   //动态生成二维数组mg->a[i] = (ElemType*)malloc(nSize*sizeof(ElemType));for(j = 0;j < mg->n;j ++){mg->a[i][j] = mg->noEdge;  //初始化时权重都设为-1}mg->a[i][i] = 0;        //自回路设置为0}return OK;
}//邻接矩阵的撤销(改成了int型,有返回值),先释放一维数组,再释放指针数组
int Destory(mGraph *mg){int i;for(i = 0;i < mg->n;i ++){free(mg->a[i]);  //释放n个一维数组的存储空间}free(mg->a);         //释放一维数组的存储空间return 1;
}//邻接矩阵的边的搜索
Status Exist(mGraph *mg,int u,int v){if(u < 0||v < 0||u > mg->n-1||v > mg->n-1 ||u == v||mg->a[u][v] == mg->noEdge) return ERROR;return OK;
}//邻接矩阵的边的插入
Status Insert(mGraph *mg,int u,int v,ElemType w){if(u < 0||v < 0||u > mg->n-1||v > mg->n-1 ||u == v) return ERROR;if(mg->a[u][v] != mg->noEdge) return Duplicate;  //若待插入边已存在,则返回出错信息mg->a[u][v] = w;                                 //插入新边mg->e ++;                                        //增加一条边return OK;
}//邻接矩阵的边的删除
Status Remove(mGraph *mg,int u,int v){if(u < 0||v < 0||u > mg->n-1||v > mg->n-1 ||u == v) return ERROR;if(mg->a[u][v] == mg->noEdge) return NotPresent;  //若待删除边不存在,则返回出错信息mg->a[u][v] = mg->noEdge;                         //删除边mg->e --;return OK;
}//选出最小的d[i],i ∈ V-S
int Choose(int d[],int n,int s[]){  //对教材进行了一点改动,形式参数设置为数组而不是指针,参考了陈惠南老师的《数据结构——C语言描述》int i,minpos;ElemType min;min = INFTY;minpos = -1;for(i = 0;i < n;i ++){         //这里i初值改为0if(d[i] <= min && !s[i]){  //<改为<=min = d[i];minpos = i;}}return minpos;                //返回下标位置
}//Dijkstra算法
Status Dijkstra(mGraph g,int v,int d[],int path[]){  //对教材进行了一点改动,形式参数设置为数组而不是指针,参考了陈惠南老师的《数据结构——C语言描述》int i,k,w,distance = 0;       //增加了一个distance记录最短距离之和int *s;if(v < 0||v > g.n-1){return ERROR;}s = (int*)malloc(g.n*sizeof(int));for(i = 0;i < g.n;i ++){      //初始化s[i] = 0;                 //表示顶点i是否在s中d[i] = g.a[v][i];         //v到i的距离if(i != v && d[i] < INFTY){path[i] = v;          //标识指向i的源点v}else path[i] = -1;}s[v] = 1;                     //顶点v为源点,将原点v加入集合Sprintf("%d ",v);              //输出源点0d[v] = 0;for(i = 1;i <= g.n-1;i ++){   //产生n-1条最短路径,<改为<=k = Choose(d,g.n,s);      //求当前路径最短者ks[k] = 1;                 //将k加入集合S中printf("%d ",k);for(w = 0;w < g.n;w ++){  //更新d和pathif(!s[w] && d[k]+g.a[k][w] < d[w]){d[w] = d[k] + g.a[k][w];distance = d[w];  //计算min距离path[w] = k;}}}printf("\nThe shortest distance:%d ",distance);return OK;
}int main(){mGraph g;int nSize,edge,u,v,i;int d[100];int path[100];ElemType w;printf("Please enter the size of the mgraph:");scanf("%d",&nSize);Init(&g,nSize,INFTY);printf("Please enter the number of the edges:");scanf("%d",&edge);printf("Now init the graph.\n");for(i = 0;i < edge;i ++){printf("Please enter the edge:");scanf("%d%d%d",&u,&v,&w);Insert(&g,u,v,w);}Dijkstra(g,0,d,path);return 0;
}

实验结果:

版权声明:本文为博主原创文章,未经博主允许不得转载。

这篇关于南邮数据结构实验3.5:飞机换乘最短距离(Dijkstra单源最短路径)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/343782

相关文章

Python实例题之pygame开发打飞机游戏实例代码

《Python实例题之pygame开发打飞机游戏实例代码》对于python的学习者,能够写出一个飞机大战的程序代码,是不是感觉到非常的开心,:本文主要介绍Python实例题之pygame开发打飞机... 目录题目pygame-aircraft-game使用 Pygame 开发的打飞机游戏脚本代码解释初始化部

SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志

《SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志》在SpringBoot项目中,使用logback-spring.xml配置屏蔽特定路径的日志有两种常用方式,文中的... 目录方案一:基础配置(直接关闭目标路径日志)方案二:结合 Spring Profile 按环境屏蔽关

VSCode设置python SDK路径的实现步骤

《VSCode设置pythonSDK路径的实现步骤》本文主要介绍了VSCode设置pythonSDK路径的实现步骤,包括命令面板切换、settings.json配置、环境变量及虚拟环境处理,具有一定... 目录一、通过命令面板快速切换(推荐方法)二、通过 settings.json 配置(项目级/全局)三、

使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)

《使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)》字体设计和矢量图形处理是编程中一个有趣且实用的领域,通过Python的matplotlib库,我们可以轻松将字体轮廓... 目录背景知识字体轮廓的表示实现步骤1. 安装依赖库2. 准备数据3. 解析路径指令4. 绘制图形关键

如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)

《如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)》:本文主要介绍如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)问题,具有很好的参考价值,希望对大家有所帮助,如有... 目录先在你打算存放的地方建四个文件夹更改这四个路径就可以修改默认虚拟内存分页js文件的位置接下来从高级-

一文详解如何查看本地MySQL的安装路径

《一文详解如何查看本地MySQL的安装路径》本地安装MySQL对于初学者或者开发人员来说是一项基础技能,但在安装过程中可能会遇到各种问题,:本文主要介绍如何查看本地MySQL安装路径的相关资料,需... 目录1. 如何查看本地mysql的安装路径1.1. 方法1:通过查询本地服务1.2. 方法2:通过MyS

Python如何调用指定路径的模块

《Python如何调用指定路径的模块》要在Python中调用指定路径的模块,可以使用sys.path.append,importlib.util.spec_from_file_location和exe... 目录一、sys.path.append() 方法1. 方法简介2. 使用示例3. 注意事项二、imp

使用Python实现矢量路径的压缩、解压与可视化

《使用Python实现矢量路径的压缩、解压与可视化》在图形设计和Web开发中,矢量路径数据的高效存储与传输至关重要,本文将通过一个Python示例,展示如何将复杂的矢量路径命令序列压缩为JSON格式,... 目录引言核心功能概述1. 路径命令解析2. 路径数据压缩3. 路径数据解压4. 可视化代码实现详解1

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Linux修改pip和conda缓存路径的几种方法

《Linux修改pip和conda缓存路径的几种方法》在Python生态中,pip和conda是两种常见的软件包管理工具,它们在安装、更新和卸载软件包时都会使用缓存来提高效率,适当地修改它们的缓存路径... 目录一、pip 和 conda 的缓存机制1. pip 的缓存机制默认缓存路径2. conda 的缓