没有合适的资源?快使用搜索试试~ 我知道了~
试设计一个算法,求图中一个源点到其他各顶点的最短路径
4星 · 超过85%的资源 需积分: 35 89 下载量 190 浏览量
2011-05-27
18:21:24
上传
评论 5
收藏 485KB DOC 举报
温馨提示
试读
15页
试设计一个算法,求图中一个源点到其他各顶点的最短路径。 (1)用邻接表表示图; (2)按长度非递减次序打印输出最短路径的长度及相应路径。
资源推荐
资源详情
资源评论
数据结构实习报告
(三)
学号:
班级:
姓名:
实习三 图及其应用
题目:试设计一个算法,求图中一个源点到其他各顶点的最短路径。
一.需求分析:
(1)用邻接表表示图;
(2)按长度非递减次序打印输出最短路径的长度及相应路径。
二.设计思想:
本程序使用链表的形式存储的。根据书上的德克斯德拉算法的思想,初始状态
时,集合 s 中只包含源点,设为 v0,然后不断地从集合 T 中选择到源点 v0 路径长
度最短的结点 u 加入到集合 s 中,集合 s 中每加入一个新的结点 u 都要修改从源点
v0 到集合 T 中剩余结点的当前最短路径长度值,集合 T 中各结点的新的当前最短
路径的长度值,为原来的最短路径的长度值与从源点过结点 u 到达该结点的路径
长度中的最小者。此过程不断地重复,直到集合 T 中的结点全部加入到集合 s 中为
止。
三.设计提示
题中规定采用邻接表表示图,假设图中有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)。
四.设计思想
构图比较简单。求最短路径是修改的书上的 Dijkstra 函数,书上的图是用邻接矩阵存储的,
我按照题目要求改为邻接链表,但是思想一样。排序借用了冒泡排序法。输出最短
路径是自己设计的一个递归函数。函数体如下:
void Dijkstra(AdjLGraph G, int v0, int distance[], int path[])
/*带权图 G 从下标 v0 顶点到其它顶点的最短距离 distance*/
/*和最短路径下标 path*/
{ Edge *p;
int n=G.numOfVerts;
int *s = (int *)malloc(sizeof(int)*n);
int minDis, i,j,u;
/*初始化*/
构图
求最短路径
打印
输入点边
信息
调用 creatgraph
排序
输出(可用递归)
剩余14页未读,继续阅读
dadadadadagegegegege
- 粉丝: 0
- 资源: 4
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
- 1
- 2
前往页