c语言求一点到多点最短路径长度,C语言迪杰斯特拉实现最短路径算法(14页)-原创力文档...
发布日期:2021-10-31 14:06:55 浏览次数:11 分类:技术文章

本文共 1992 字,大约阅读时间需要 6 分钟。

数据结构课程设计报告

----旅游咨询系统设计

目录

一、需求分析

二、系统分析

三、概要设计

一、 系统划分

二、 邻接矩阵建立流程图:

三、 迪杰斯特拉算法流图

四、详细设计

五、调试分析

一、运行结果

二、改进设想

六、课设总结

旅游咨询系统设计

一、需求分析

在交通网络日益发达的今天,人们出行有很多种方式、路线,而如何选择符合需要的方式路线成为大家的一大难题。所以,在此我利用计算机建立一个旅游咨询系统。在系统中采用图来构造各个城市之间的联系,图中顶点表示城市,边表示各个城市之间的路线,所带权值为两个城市间的路程、时间或车费等。这个交通咨询系统可以回答旅客提出的各种问题,例如:如何选择一条路径使得从A城到B城里程最短;如何选择一条路径使得从A城到B城花费最低;如何选择一条路径使得从A城到B城所用的时间最少等等的一系列问题。

二、系统分析

设计一个旅游咨询系统,能咨询从任何一个城市顶点到其他城市顶点之间的最短路径(里程、最低花费或是最少时间等问题。对于不同的咨询要求,可输入城市间的路程、所需时间或是所需费用等信息。旅客可以在同一个系统中综合考虑自己的各目标城市,选择一个最佳的旅游路线和出行方式。

针对最短路径问题,在本系统中采用图的相关知识,采用了迪杰斯特拉算法,解决在实际情况中的最短路径问题,而迪杰斯特拉算法的时间复杂度为O(n2,空间复杂度为O(n。本系统使用邻接矩阵存储无向图。其中,建立矩阵的时间复杂度为O(n2,但是利用其查找一条边的时间复杂度为O(1。本系统中包括了利用邻接矩阵建立图的存储结构和单源最短问题两大部分,使用指针数组实现利用一个程序实现最短路径和最短时间的运算。并且本系统设置了人性化的系统提示菜单,方便使用者的使用。

三、概要设计

一、 系统划分

该系统可以划分为三个部分:

1、 利用邻接矩阵建立图的存储结构;

2、 利用迪杰斯特拉算法解决单源最短路径问题;

3、 实现城市之间的最短路径问题和最短时间问题。

二、 邻接矩阵建立流程图:

四、详细设计

本课程设计的源程序如下所示:

#include

#include

#define MVNum 100

#define Maxint 9999 /*将无穷大的数值设为9999*/

typedef char vertextype;/*建立无向图*/

typedef int adjmatrix;

typedef struct

{

vertextype vexs[MVNum];

adjmatrix arcs[MVNum][MVNum];

}mgraph;

mgraph *G[2]; /*设置指针数组用以实现距离和时间最小值求取*/

void city_number( /*输出城市代表序号*/

{ printf("*************************************************************************\n";

printf(" 1、北京 2、上海 3、香港 4、天津 5、重庆 6、澳门 7、哈尔滨 8、石家庄";

printf(" \n 9、兰州 10、昆明 11、成都 12、长春 13、沈阳 14、长沙 15、海口 16、西安";

printf("\n*************************************************************************\n";

}

void Createmgraph(int a,int n,int e /*建立无向邻接矩阵*/

{int i,j,k;

int w;

for(i=1;i<=n;i++

for(j=1;j<=n;j++

if(i==j G[a]->arcs[i][j]=0; /*邻接矩阵对角线初始值设为0*/

else G[a]->arcs[i][j]=Maxint; /*其他元素设为无穷大*/

for(k=1;k<=e;k++ /*读入e条边数的信息*/

{printf("\n输入图中各起点终点及其权值i,j,w:"; /*读入无向边及其权值*/

scanf("%d,%d,%d",&i,&j,&w;

G[a]->arcs[i][j]=w;

G[a]->arcs[j][i]=w;

}

}

void Dijkstra(int a,int v0,int N/*Dijkstra算法的实现和打印*/

{

enum boolean S[MVNum]; /*终点集合*/

int dist[MVNum],path[MVNum]; /*dist表示源点v0到图中其余顶点的最短长度,path表示其对应的路径*/

int i,wmin,u,num=1,k;

for(i=1;i<=N;i++ /*数组dist和集合S付初值*

转载地址:https://blog.csdn.net/weixin_39975900/article/details/117208208 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:c语言检测数独是否正确,会数独的大佬请进。这是个判断九宫格数独是否正确的程序。...
下一篇:c语言读取csv部分数据,C语言进行csv文件数据的读取

发表评论

最新留言

表示我来过!
[***.240.166.169]2024年03月09日 23时13分50秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

mysql call_mysql的call用法 call调用函数的例子 2019-04-21
python参数验证_参数验证,Python中的最佳实践 2019-04-21
python画多层网络_在pymn中修改多层网络图 2019-04-21
java net 安卓_android -------- java.net.UnknownServiceException 2019-04-21
java 密钥 aes 解密_Java中AES加密解密以及签名校验 2019-04-21
java树转化成图_Java 转换一组数据为树型数据 2019-04-21
java 底层ppt_Java 如何设置 PPT 中的形状排列方式 具体内容 2019-04-21
mysql service5.7_Mysql5.7服务下载安装 2019-04-21
mysql查看线程完整执行命令_MySQL-查看运行的线程-SHOW PROCESSLIST 2019-04-21
mysql 更新数据 字符串_批量替换 MySQL 指定字段中的字符串 2019-04-21
web开发 mysql安装_mysqlinstallerwebcommunity5.7.21.0.msi安装图文教程 2019-04-21
mysql concat 整数型_MySQL 数字类型转换函数(concat/cast) 2019-04-21
mysql单元格函数是_MySQL常用内置函数 2019-04-21
mysql 怎么字段分裂_你可以分裂/爆炸MySQL查询中的字段吗? 2019-04-21
mysql server卸载出错_Mysql卸载问题Start Server卡住报错解决方法 2019-04-21
全国省市区 mysql_2017全国省市区数据库【含三款数据库】 2019-04-21
druid加载MySQL驱动原理_你好,想知道mybatis+druid+jdbc 原理介绍? 2019-04-21
mysql 怎样链接jdbc_jdbc怎么链接mysql数据库 2019-04-21
mysql学生课程表试题_Mysql练习之 学生表、课程表 、教师表、成绩表 50道练习题... 2019-04-21
java exec封装_Java 执行系统命令工具类(commons-exec) 2019-04-21