用贪心算法解单源最短路径问题_贪心算法单源最短路径问题,单源最短路径问题贪心算法 - CSDN文库

5星 · 超过95%的资源需积分: 47 49 浏览量更新于2023-07-10 评论 2 收藏 62KB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

实验项目名称：用贪心算法解单源最短路径问题

一、实验目的：

明确单源最短路径问题的概念；利用贪心算法解决单源最短路径问题；并通过本例熟悉贪心算法在

程序设计中的应用方法。

二、实验原理：

贪心算法原理：在贪婪算法（greedy method）中采用逐步构造最优解的方法。在每个阶段，都作出一

个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪婪决策的依据称为贪

婪准则（greedy criterion）。

三、实验内容与步骤：

问题描述：

求网（带权有向图）中从一个顶点到其余各顶点间的最短路径。

一个有向图 G，它的每条边都有一个非负的权值 c[i,j]，“路径长度”就是所经过的所有边的权值之和。对

于源点需要找出从源点出发到达其他所有结点的最短路径。

基本思想　分步求出最短路径，每一步产生一个到达新目的顶点的最短路径。下一步所能达到的目的顶

点通过如下贪婪准则选取：在未产生最短路径的顶点中，选择路径最短的目的顶点。设置顶点集合S并

不断作贪心选择来扩充这个集合。当且仅当顶点到该顶点的最短路径已知时该顶点属于集合S。初始时

S中只含源。设u为G中一顶点，我们把从源点到u且中间仅经过集合S中的顶点的路称为从源到u特殊路

径，并把这个特殊路径记录下来（例如程序中的dist[i]）。每次从V-S选出具有最短特殊路径长度的顶

点u，将u添加到S中，同时对特殊路径长度进行必要的修改。一旦V=S，就得到从源到其他所有顶点的

最短路径，也就得到问题的解。

如上图所示，编程实现求从任一顶点出发到其它顶点的最短路径长度。

如下：

please input the first number:0

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余7页未读，立即下载

评论3

zengbing

2013-12-13

一般般吧，要是再生动形象点就好了

lsrlst

粉丝: 35
资源: 6

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈