数据结构课程设计(最短路径Dijkasta算法) 本课程设计的目标是解决供货中的路径问题,通过设计算法来求取某城市一公司对其在下的子商场供货最短路径,以减少公司的运输成本,获得更大的利润。为此,我们将熟悉最短路径算法——Dijkasta算法,并运用图论的知识来解决实际问题。 一、课程设计目的 本课程设计的目的旨在解决供货中的路径问题,设计算法求取某城市一公司对其在下的子商场供货最短路径。在某种程度上减少其公司的运输成本,获得更大的利润。通过运用图论的最短路径知识来解决实际问题,旨在更深刻的学习此门课的知识,提高我们的动手实践能力,提高我们的自主分析、设计程序能力和综合运用我们所学的知识的能力。 二、课程设计内容 某城市一公司总部设在 A 处,旗下的子商场有 B、C、D、E、G、H。每天都必须给每个商场配送共同的货物和一些不相同的货物,设计一个程序解决每天给每个商场供货所走的最短路线。已知其各地相距的距离如下表: | 起点 | 终点 | 距离 | | --- | --- | --- | | A | B | 130 | | A | C | 80 | | A | D | 260 | | B | D | 75 | | C | E | 50 | | D | E | 120 | | B | F | 265 | | D | F | 85 | | D | G | 400 | | E | G | 350 | | F | G | 120 | | H | G | 200 | | H | E | 150 | 程序的功能应包含: (1)输出点的信息,各地的位置; (2)输出边的信息,即两地的路径的权; (3)A 地到其他的商场的的最短路径,为公司提供供货的最短路径; (4)读出两地的最短路径,为两商场之间的货物相互调运,协调提供最短路径。 三、相关的知识 解决此问题,设计的程序主要运用 Dijkasta 算法,其思想:设置两个顶点集合,其中一个集合存放已找到的最短路径顶点,另一个集合存放当前的还未找的最短路径顶点。初始状态,只包含原点,然后从其中选择到原点最短的路径的点加入到中,集合中每加入一个新的点都要修改原点到中的剩余点的当前的最短路径长度值,集合中各顶点的新的当前的最路径长度值,为原来的当前的最短路径长度值与从原点过新加入的点到达该顶点的路径长度中的最小的者。此过程直到集合全部加入到为止。 图的邻接矩阵作为存储结构来存放连点之间的信息即位置,带权值。为了方便把程序设计成模化类。 四、核心算法 本程序设计的功能实现主要是采用主函数调用其他的函数模块,采用 Switch 选择调用。如下: void main(){ 初始化; while(“命令”!=“退出”){ Switch 语句 接受命令(输入选择项序号); 处理命令; }} 以下主要介绍调用的 Dijkstra(MGraph * G)函数,其他的函数模块详见附录·代码。 1. 主要的数据结构与算法 typedef struct //图中顶点表示点,存放点名称 void Menu() //输出菜单 void PutOutVex(MGraph *G) //输出每个顶点的信息 void PutOutArc(MGraph *G) //输出每条边的信息 void Dijkstra(MGraph * G) //狄克斯特拉算法求最短路径 void main() //主函数 2. 寻找最短路径的算法 void Dijkstra(MGraph * G) //狄克斯特拉算法求最短路径 { int v,w,i,min,t=0,x,v0,v1; int final[20], D[20], p[20][20]; cout<<"请输入起点:\n"; cin>>v0; if(v0<0||v0>G->vexnum) { cout<<"此点编号不存在!请重新输入顶点编号:"; cin>>v0; } cout<<"请输入结束顶点:\n"; cin>>v1; if(v1<0||v1>G->vexnum) { cout<<"此点编号不存在!请重新输入顶点编号:"; cin>>v1; } for(v=0;v<G->vexnum;v++) {// 初始化 final[20],p[20][20],fin














剩余8页未读,继续阅读

- yll21212013-06-09对于路径的算法挺好的,实用
- 太原水哥2013-10-10帮助很大,推荐新手采纳
- gglad2012-08-09写论文的时候 用的 不错~

- 粉丝: 7
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助


最新资源
- 以用户为中心的互联网运营体系(腾讯).1(ppt文档).ppt
- 数字图像处理与分析-8图像分割.ppt
- 网络营销成功案例之麦包包.ppt
- 数据结构c语言版严蔚敏1.ppt
- 综合布线系统认识与标准机柜拆装手册.pptx
- 国家开放大学电大《教育学》网络课形考任务4作业及答案.docx
- 互联网“加”时代传统企业创新转型升级的商业财税收视角.pptx
- 企业安全教育多元化、层次化、网络化思路初探.doc
- 计算机教师年终工作总结大全10篇.docx
- 办公设备使用管理制度.doc
- 项目管理案例分析作业.doc
- 电子商务认识实习总结.docx
- 基于网站的分析与设计.doc
- 企业网络解决方案思科设备.doc
- 网络咨询的技巧与责任.ppt
- 项目管理九大模块-项目分析方法[最终版].pdf


