没有合适的资源?快使用搜索试试~ 我知道了~
带权图求最短路径课程设计报告
4星 · 超过85%的资源 需积分: 9 25 下载量 111 浏览量
2011-07-21
15:52:26
上传
评论 1
收藏 281KB DOC 举报
温馨提示
试读
16页
带权图求最短路径:如果给出了一个带权图,则可以试设计一个算法,求图中一个源点到其他各顶点的最短路径。试编写实现上述功能的程序。已知带权图,设计完成下列任务的一个算法: (1)用邻接表表示图; (2)按长度非递减次序打印输出最短路径的长度及相应路径。
资源推荐
资源详情
资源评论
《数据结构》课程设
计
求最短路径
指导教师:
设计人:
班级:
学号:
设计时间:2011 年 5 月 6
实习三 图及其应用
题目:求最短路径 实习时间:2011.5.6
一、需求分析:
1. 如果给出了一个带权图,则可以试设计一个算法,求图中一个源点到其他各顶点的最短
路径。试编写实现上述功能的程序。已知带权图,设计完成下列任务的一个算法:
(1)用邻接表表示图;
(2)按长度非递减次序打印输出最短路径的长度及相应路径。
2.测试数据:
二、设计:
设计思想
(1)存储结构:链表的形式存储,采用邻接表表示图,假设图中有 n 个顶点,则考虑邻接
表表头结点为 head[0],head[1],head[2],…,head[n-1],链表中每个结点有三个字段:其
中,vertex----顶点字段,存放顶点序号;cost----表头顶点到该顶点之边上的权值;link----
连接同一链中的下一个顶点。
(2)主要算法基本思想:本程序主要应用了狄克斯特拉算法的思想来寻找最短路径。
设计表示
(1)函数调用关系图
main->void bulidalgraph
->void shortpath
->void putpath
(2)函数接口规格说明
main()主调函数,调用建图 、求最短路径 、输出等函数。
void bulidalgraph(algraph *g);建图函数,调用判断函数 locatvex
void shortpath(algraph *g,char ch);求从该节点出发到达各个路径的最短路径
void putpath(algraph *g,int i);输出路径函数
int locatvex(algraph *g,char ch);判断 ch 是否在最新的最短路径集合中,在的就跳出
否则就申请一个动态链表存储
详细设计
采用邻接表表示图,假设图中有 n 个顶点,则考虑邻接表表头结点为
head[0],head[1],head[2],…,head[n-1],链表中每个结点有三个字段:
其中,vertex——顶点字段,存放顶点序号;
cost——表头顶点到该顶点之边上的权值;
link——连接同一链中的下一个顶点。
采用数组 dist[j](0≤j≤n-1)存放从源点 v0 到顶点 vj 的最短路径长度,dist[0]=0,如果源
点 v0 到顶点 vx 无通路,则 dist[x]=max(计算机允许的最大值)。
采用 n-1 个数组分别存放源点 v0 到其余 n-1 个顶点之最短路径上的顶点(序号)。采
用数组 S 指示已找到最短路径的顶点。S[j]=0 表示顶点 j 不在数组中,S[j]=1 表示顶点 j 在
数组中(0≤j≤n-1)。
初始状态时,集合 s 中只包含源点,设为 v0,然后不断地从集合 T 中选择到源点 v0
路径长度最短的结点 u 加入到集合 s 中,集合 s 中每加入一个新的结点 u 都要修改从源点
v0 到集合 T 中剩余结点的当前最短路径长度值,集合 T 中各结点的新的当前最短路径的长
度值,为原来的最短路径的长度值与从源点过结点 u 到达该结点的路径长度中的最小者。
此过程不断地重复,直到集合 T 中的结点全部加入到集合 s 中为止。
总体来说,本程序设计相对比较简单,主要包括四个功能模块:
主调函数、建图函数 、求最短路径函数 、输出函数。
下面分别给予介绍:
主调函数
main()
{
void bulidalgraph(algraph *g);
void shortpath(algraph *g,char ch); //求从该节点出发到达各个路径的最短路径
void putpath(algraph *g,int i); //输出路径
int locatvex(algraph *g,char ch);
algraph g;
arcnode *p;
int i;
char ch;
int tag=1;
bulidalgraph(&g);
for(i=0;i<g.vexnum;i++)
{
for(p=g.vertices[i].firstarc;p;p=p->nextarc)
printf("%c,%c ",g.vertices[i].data,g.vertices[p->adjvex].data);
printf("\n");
}
剩余15页未读,继续阅读
资源评论
- 塔罗御风2012-05-24内容有点混乱,没按照标准的报告做。
- 偶是俊婷2012-12-18有点乱 学得不好 没看懂
cqq20091001234
- 粉丝: 2
- 资源: 10
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功