专栏首页云时之间算法导论系列:贪心算法(2)
原创

算法导论系列:贪心算法(2)

这篇文章我们将来一起看看贪心算法一个具体例子, Dijkstra算法

Dijkstra算法最著名的应用是解决单元最短路径,这是一类贪心算法,他先是求出长度最短的一条路径,然后参照这一条最短路径去求出长度次短的路径,知道求出从起点到各个定点的最短路径.

这个算法不仅仅是贪心算法,其实也是一种特殊的动态规划,动态规划的本质是独立的子问题,而贪心每次可以求得最优的独立子问题,这两者有一些交集,但是收到很多约束,会影响适应的范围.

举例:今天你去一个景点去玩,景点地图如下,假如你从1号点出发,那到达其他各个节点的最短路径是什么?

现在我们假设景点地图如上所示,从起点到下一个点都会有具有方向路径和相应的权重,我们可以使用矩阵进行表示,如下图所示:

下图是算法的过程(用电子屏幕写字果然很不舒服):

最终的路径为:

代码如下:

运行结果:

1:输入样例

2:输出结果

下一篇文章我们将一起学习下哈夫曼编码

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法导论系列:贪心算法(2)

    现在我们假设景点地图如上所示,从起点到下一个点都会有具有方向路径和相应的权重,我们可以使用矩阵进行表示,如下图所示:

    云时之间
  • 机器学习常用算法分类(2)

    感谢大家的关注,在上一篇文章中发布后很多热心的小伙伴建议我可以改进下分类的方式,一种是根据学习的方式分类,另外一种是根据类似的形式或者功能进行分类,我几天一直在...

    云时之间
  • 算法导论系列:贪心算法(1)

    周末开始着手算法这一系列文章,说起写这一系列的初衷是发现网上很多的同学们在学习算法这个时候,会遇到很多困难,而学校书中讲的道理尽管很对,但是总是太过于晦涩,正确...

    云时之间
  • 算法导论系列:贪心算法(2)

    现在我们假设景点地图如上所示,从起点到下一个点都会有具有方向路径和相应的权重,我们可以使用矩阵进行表示,如下图所示:

    云时之间
  • [图]最短路径-Dijkstra算法

    2.BFS可能会是Dijkstra算法的实质,BFS使用的是队列进行操作,而Dijkstra采用的是优先队列。

    王荣胜
  • 知其所以然(以算法学习为例)

    其实下文的绝大部分内容对所有学习都是同理的。只不过最近在正儿巴经地学算法,而后者又不是好啃的骨头,所以平时思考总结得就自然要比学其它东西要多一些。 问题:目前几...

    前朝楚水
  • 书单丨从0起步探秘算法世界 畅享编程之趣

    本书围绕程序设计典型算法,编织了一个扣人心弦又趣味横生的侦探缉凶故事。小说主人公运用高超的搜索技巧和精深的算法知识,最终识破阴谋、缉拿元凶,让你在愉悦的沉浸式体...

    博文视点Broadview
  • 基于蚁群算法的机械臂打孔路径规划

      该问题来源于参加某知名外企的校招面试。根据面试官描述,一块木板有数百个小孔(坐标已知),现在需要通过机械臂在木板上钻孔,要求对打孔路径进行规划,力求使打孔总...

    waylon
  • 网络免疫的组合跟踪方法

    原文标题:Combinatorial Trace Method for Network Immunization

    李欣颖6837176
  • 数据工程师的算法!

    翻出来了17年自己梳理的数据工程师的算法学习内容,当时的理解和现在会有些许不同,但整体来看还是可以的,有一些比较细节的内容并没有花较多的时间来整理,留待大家自己...

    木东居士

扫码关注云+社区

领取腾讯云代金券