- 1、本文档共12页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
《算法设计与分析》
课程设计报告
题 目: 求带权最短路径
专 业: ****
学 号: ****
姓 名: ****
指导教师: ***
成 绩:
** 年 *月 ** 日
一、问题描述
给定n个 顶点的带权有向图G=(V,E),W=()为G的带权邻接矩阵。定义如下:=
对于每一对顶点u,vV,试用动态规划方法,求从u到v的带权最短路径长度,其中路径权值为这条路径所有边上的权值之和。
二、设计说明
1、基本要求:利用Dijkstra算法,寻找有向图中最短路径 。
2、算法说明:Dijkstra算法是由荷兰计算机科学家艾兹格·迪科斯彻发现的。算法解决的是有向图中最短路径问题。 Dijkstra算法的输入包含了一个有权重的有向图G,以及G中的一个来源顶点S。 我们以V表示G中所有顶点的集合。图中的每一个边,都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。 假设E为所有边的集合,而边的权重则由权重函数w: E → [0, ∞]定义。 因此,w(u,v)就是从顶点u到顶点v的非负花费值(cost)。 边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值,就是该路径上所有边的花费值总和。 已知有V中有顶点s及t,Dijkstra算法可以找到s到t的最低花费路径(i.e. 最短路径)。 这个算法也可以在一个图中,找到从一个顶点s到任何其他顶点的最短路径。
这个算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。初始时,源点s的路径长度值被赋为0(d[s]=0), 同时把所有其他顶点的路径长度设为无穷大,即表示我们不知道任何通向这些顶点的路径(对于V中所有顶点v除s外d[v]= ∞)。当算法结束时,d[v]中储存的便是从s到v的最短路径,或者是无穷大(如果路径不存在的话)。 Dijstra算法的基础操作是边的拓展:如果存在一条从u到v的边,那么从s到v的最短路径可以通过将边(u,v)添加到s到u的尾部来拓展。这条路径的长度是d[u]+w(u,v)。如果这个值比目前已知的d[v]的值要小,我们可以用新值来替代当前d[v]中的值。拓展边的操作一直执行到所有的d[v]都代表从s到v最短路径的花费。这个算法经过适当的组织因而当d[u]达到它最终的值的时候,每条边(u,v)都只被拓展一次。 算法维护两个顶点集S和Q。集合S保留了我们已知的所有d[v]的值已经是最短路径的值顶点,而集合Q则保留其他所有顶点。集合S初始状态为空,而后每一步都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的d[u]值的顶点。当一个顶点u从Q中转移到了S中,算法对每条外接边(u,v)进行拓展。
3、算法思想:
(1)设S为最短距离已确定的顶点集(看作红点集),V-S是最短距离尚未确定的顶点集(看作蓝点集)。 ①初始化:初始化时,只有源点s的最短距离是已知的(SD(s)=0),故红点集S={s},蓝点集为空。 ②重复以下工作,按路径长度递增次序产生各顶点最短路径。在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集,以保证按路径权重递增的次序来产生各顶点的最短路径。当蓝点集中仅剩下最短距离为∞的蓝点,或者所有蓝点已扩充到红点集时,s到所有顶点的最短路径就求出来了。
注意:①若从源点到蓝点的路径不存在,则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径。 ②从源点s到终点v的最短路径简称为v的最短路径;s到v的最短路径长度简称为v的最短距离,并记为SD(v)。 (2)在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集 根据按长度递增序产生最短路径的思想,当前最短距离最小的蓝点k的最短路径是: 源点,红点1,红点2,…,红点n,蓝点k 。距离为:源点到红点n最短距离+红点n,蓝点k边长 为求解方便,设置一个向量D[0..n-1],对于每个蓝点v∈ V-S,用D[v]记录从源点s到达v且除v外中间不经过任何蓝点(若有中间点,则必为红点)的最短路径长度(简称估计距离)。 若k是蓝点集中估计距离最小的顶点,则k的估计距离就是最短距离,即若D[k]=min{D[i] i∈V-S},则D[k]=SD(k)。 初始时,每个蓝点v的D[c]值应为权ws,v,且从s到v的路径上没有中间点,因为该路径仅含一
您可能关注的文档
- 继电盒盖课程设计说明书.doc
- 简易波形发生器课程设计报告.doc
- 简易电子琴单片机课程设计.doc
- 简易示波器课程设计报告.doc
- 简易自动电阻测试仪设计周记.doc
- 简易自动油烟机控制系统毕业设计.doc
- 胶带输送机减速器课程设计.doc
- 节流变压降流量计课程设计.doc
- 结构设计原理课程设计---钢筋混凝土单向肋梁楼盖设计书.doc
- 结合支持向量机的特征选择方法在信用评估中的应用外文翻译.doc
- 浙江省临海市白云高级中学2025届高三历史3月月考试题.doc
- 云南拾谷县第一中学2024_2025学年高二物理上学期10月月考试题.doc
- 2025版高考生物总复习第13讲基因的分离定律教案苏教版.doc
- 湖北省黄石实验高中2024_2025学年高一历史下学期期末考试模拟卷.doc
- 通史版2025版高考历史大一轮复习专题七近代化的曲折发展__中日甲午战争至五四运动前4第4讲从维新思想到新文化运动课后达标检测含解析新人教版.doc
- 2024年高考数学考试大纲解读专题04导数及其应用含解析文.doc
- 河南省许汝平九校联盟2024_2025学年高一语文上学期期末考试试题扫描版无答案.doc
- 江西省吉安市吉水县第二中学2024_2025学年高一历史上学期第二次月考试题.doc
- 北京市平谷区2025届高三政治一模考试试题含解析.doc
- 2025届中考物理第四讲物态变化专项复习测试无答案新人教版.docx
文档评论(0)