文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > 第八章_贪心算法
侵权投诉

第八章_贪心算法

结论0-1背包问题能用动态规划法解,但不能用贪心法解。

8.3单源最短路径问题(狄斯奎诺Dijkstra’s算法)

一、问题描述

G (V,E)是一个有向图,每条边上有一个非负整数表示长度值,其中有一

个顶点s称为源节点。所谓的单源最短路径问题就是:求解该源节点到所有其它节点的最短路径值。不失去一般性,我们假设V {1,2,3,...,n}并且s=1。那么该问题可以使用Dijkstra’s算法来求解,该算法是一种贪心算法,并且能求得最优解。

二、算法思想

开始时,我们将所有的顶点划分为两个集合X {1},Y {2,3,4,..,n}。所有已经计算好的顶点存放在X中,Y中表示还没有计算好的。Y中的每个顶点y有一个对应的量 [y],该值是从源顶点到y(并且只经由X中的顶点)的最短路径值。

(1) 下面就是选择一个 [y]最小顶点y Y,并将其移动到X中。

Y中每个和y相邻的顶点w的 [w]都要更(2) 一旦y被从Y移动到X中,

新:表示经由y到w的一条更短的路径被发现了。

对于任意一个顶点 v V,假如我们使用 [v]表示源顶点到顶点v的最短路径,最后,我们可以证明上述的贪心法结束后有 [v] [v]。

三、算法DIJKSTRA

输入:含权有向图G=(V,E), V={1,2, n} 输出:G中顶点1到其他顶点的距离

上一页第4页

你可能喜欢

  • 杭电ACM
  • 动态规划算法
  • 贪心算法论文
  • 算法设计论文
  • 程序算法

热门文档

相关文档

  • 8第八章 贪心算法

    第八章 贪心算法 8.1 8.2 8.3 8.4 8. 5 引言 最短路径问题 最小耗费生成树(Kruskal算法) 最小耗费生成树(Prim算法) 文件压缩 8.1 引言● 贪心算法...

  • 第八章贪心算法

    第八章 贪心算法第十讲:黄丽韶 ly_sa@qq.com 1 ? 贪心算法的概念。 目 录 ? 贪心算法的基本要素 ① 最优子结构性质 ② 贪心选择性质 ? 通过应用范例...

  • 第八章 贪心算法

    第八章 贪心算法_物理_自然科学_专业资料。第三部分 最先割技术第八章 贪心算法 第九章 图的遍历 本章采用知识发明的第三条线,即 “方法——应用”为主线...

  • 8贪心算法

    8第八章 贪心算法 51页 7下载券 第8章 贪心算法 38页 免费 第8章 贪心...贪心算法 ---总是作出现在看来最好的选择。 顾名思义,贪心算法总是作出在当前...

  • 第8讲贪心算法

    第8章 贪心算法 48页 免费 第八章贪心算法 47页 1下载券 第八章_贪心...第8讲 贪心算法 1 所谓“贪心算法”是指:在对问题求解时,总是作出在当前看来...

  • 贪心算法

    如果这个无法证 明,贪心算法所得的解不是最优解,一般只是较优 解(较优解可为搜索剪枝提供方便)。 下面是贪心算法最经典的例子:部分背包问题。 (下一章会讲到...

  • 第四章贪心算法

    第四章 贪心算法 2012-5-27 计算机算法设计与分析 1 贪心算法的特点 ? 贪心算法总是作出在当前来看是最好的选择。 ? 就是说,贪心算法并不从整体最优上来...

  • 贪心算法

    实验四 贪心算法 实验四 贪心算法(一) 实验目的 、实验目的通过编程实现有关的... 第4章贪心算法 98页 1下载券 贪心与归纳算法 47页 1下载券...

  • 贪心算法

    贪心算法_工学_高等教育_教育专区。贪心算法主讲人:张云聪 目录什么是贪心算法... 第4章贪心算法 98页 1下载券 贪心与归纳算法 47页 1下载券...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email