像名字一样容易忘记的Dijkstra

作者: dugangabc | 来源:发表于2016-02-06 17:58 被阅读293次

Dijkstra算法是经典的求解一个顶点到其他顶点的最短距离的算法。每次学习的时候总是觉得思路简单明了,但每当要用到时,就忘记了实现的细节。归根结底还是应用的少。相信做地图导航的应该对其如数家珍。另一个难记的是这个算法名字本身。Dijkstra有点违反通常意义的单词拼写逻辑。今天决心写一篇文章,让它好记,忘不掉!

记名字

首先看算法的名字,Dijkstra中文名称为“迪杰斯特拉”。如何记忆呢?首先要记住这个单词开头是字母D,我想这个恐怕学过的人都能记住。然后呢,你会发现D后面紧跟着的居然是ijk。这三个字母可是写循环时最常用的局部变量名称了,在字母表中也是亲兄弟(挨着)。记到这里实际上最难记的部分已经搞定了。后面的stra对应中文“斯特拉”,是比较好记的。

记算法

下面再看算法本身的记忆。Dijkstra算法最核心思想就一句话:不断找最经济的新目的地。

假设有十个顶点1-10,要计算顶点1到其余顶点的最短距离。常规思维需要逐个计算顶点1到顶点2-10的最短距离。虽然这样在逻辑上很顺,但并不符合图的逻辑。按照图的逻辑,可能顶点1仅与顶点10相联,应该先计算到顶点10的最短距离更方便。这也是这个算法比较“别扭”的地方,也是容易忘记的原因。

换句话说,Dijkstra算法实际上并不关注本次计算的最小距离是到哪个顶点的。其仅关注本次所求之距离已经是最小的了。做个类比,如果把顶点比作旅游景点,起始点为出发位置,则算法首先考虑旅游的经济性,再考虑是否去了所有的地方。

下面对Dijkstra算法按图的逻辑进行描述,会发现一切都顺理成章。

  1. 设置起点v
  2. 审视参考以前去过的路径,找出可以到达没去过顶点的所有路径
  3. 若有,则选择其中代价最小的路径。并标记本次去过的顶点,执行步骤2
  4. 若没有,则结束

采用这样的策略可以保证每去一个顶点都是基于以前总结的最优经验的。使得路径的代价最小。不知道现实中有没有人这样玩。

相关文章

  • 像名字一样容易忘记的Dijkstra

    Dijkstra算法是经典的求解一个顶点到其他顶点的最短距离的算法。每次学习的时候总是觉得思路简单明了,但每当要用...

  • 2018-05-07

    今天学习狄克斯特拉算法,为了尊敬发明人,必须用他的名字dijkstra's algorithm ,dijkstra...

  • 图论模板总结

    前言:图论那几个算法真的比较容易忘记,今天就来复习一下吧 0X00 模板总结 Dijkstra 算法本身就是用来求...

  • 像忘记白茅针一样忘记

    你是否还记得小时候吃过的那些白茅针? 年纪越大,越怀念往昔的日子。 去上学的路上,总是要经过一段长长的田埂。那田埂...

  • 尤淑燕,这个我原来从没有听过的名字,现在却永远忘记不了。很美的名字,多么希望你真的可以像燕子一样自由。 我们每...

  • 名字像饮料一样

    我对自己说,不要不开心 我要我相信,一切的一切,终究会好 很多时候,我看到自己。看到我坐在书桌前, 在莫测的未来面...

  • 忘记

    像骏马忘记草原像雄鹰忘记蓝天像小溪忘记湖泊像落叶忘记风一样忘记我失去的东西比如听力与爱情因为失去了就不会再回来像小...

  • 长寿花

    桌上放着一盆叫“长寿花”的花。 只晓得它好看,拿来后放着,却早已经忘记了它的名字。 就像不容易记住美女的名字一样,...

  • 静止的风(诗歌)

    记住了春天 却忘记了夏天 像文字一样容易忘记笔画 那些被天空静止的风 那些花朵的休眠 都在炽热的周边徘徊 而一些重...

  • 最短路径模板

    堆优化的Dijkstra 普通Dijkstra SPFA

网友评论

    本文标题:像名字一样容易忘记的Dijkstra

    本文链接:https://www.haomeiwen.com/subject/vjkykttx.html