复习迪杰斯特拉算法有感
摘要
- 似乎大部分算法讲解缺少对迪杰斯特拉算法的形象化和感性化认识。
- 我对迪杰斯特拉算法的感性认识
- 我对迪杰斯特拉和普里姆算法的区别的简单感性概述
- 对总结了一个学习算法的方法。
流水账一样的记录
以下一些算法细节上的理解仅仅是我个人的理解。没有做好插图，很潦草。若有读者，看不懂也不必看懂。这个文章是写给未来的我自己。这里只是像记事本一样做个记录，做个记忆保存。
2022年8月25日。我又又又又把有向图的最短路径算法给忘了。
我为什么老是忘了这个东西啊？我想了想，我觉得是因为当时在学这个算法和写这个算法的时候没有形成感性层面的直观的认识和理解。
.jpg)
看的王道的视频，直接给出了三个数组，给了一个例子，然后开始讲。当时好像是暂停又暂停着听懂了，也照着讲的内容写出来了代码。甚至当时还用js和canvas绘图做出了动态的效果。然而我没有形成感性的直观的理解。
案例中带权有向图一个阻碍直观可视化的最大的问题，其实是边的权值应该表示节点之间距离的远近，然而例图不能够体现出来，只是仅仅的标了个数字。其实可以表达出来的，把一些线画长一些，一些线画短一些就可以了。但是发现王道里的这个例子还是不利于直观化。想要把图直观化还得把一些直线画成弯弯曲曲的用来表示它很长。不过凑活还能看。
.jpg)
我觉得没必要一上来就怼三个数组出来了。那是第二阶段的理解。第一阶段应该是感性认识的学习。
经过一番写写画画发现，三个数组的信息可以直接在图的节点上标注。也很直观。标数字，给节点画红圈，以及涂红。就很直观了。
.jpg)
迪杰斯特拉最短路径是一种贪心思想。它总是选择当前能拓展出去的，离最开始节点最近的待扩散节点开始往外继续拓展探索。如果遇到了已经拓展出去的节点，就看看是不是现在能“抄近路”，修改那个节点的“上一个节点”信息。拓展完了还把自己给“锁住”，表示自己这个已经是最短路径了。
最后的path数组其实就是这从最开始的点，在这个图上，一步一步拓展出去形成的一个树。
这个红色的树形状的物质在拓展扩散出去的时候呢，总是从最近处地方开始继续拓展扩散。一碰到自己这个物质本身，就把碰到的那个地方看能不能再拽短。最终直到扩散完毕。
.jpg)
这个跟最小生成树好像还有点像，都是把图生成成一棵树。但是生成树是不唯一的。生成树的普里姆算法是可以随便从一个节点开始选的，但是这个迪杰斯特拉算法是从指定的节点开始，计算从它到所有节点的最短路径的。他们倒是都用了贪心思想，总是选择最小的。
普里姆：先随便选一个节点，然后也是开始扩张，扩张的时候选择距离自己这个生成树轮廓最近的，然后纳入生成树。迪杰斯特拉是不停的选择距离最开始的那个节点最近的然后开始扩。
但普里姆在考研的数据结构里没有给出能写出代码的要求，只需要理解和手推就行了。我觉得这就算是第一阶段的算法理解程度，问题在于第一阶段的程度不能很好的体会到时间复杂度。书上也没给出代码。居然还是像集合论一样的伪代码。还是克鲁斯卡尔算法更好理解一些。直接给所有边放到数组里排个序。然后每个边取出来两端的端点两两连通就可以了。像并查集一样。如果本来就是连通的了就pass。所以时间复杂度很容易就看出来是NlogN级别，因为是排序。后面的并查集一样的检测连通是N级别的。所以省略了。普里姆算法怎么看都像是超过N²的。
普里姆算法现在只是停留在第一阶段了。休息一下，先学更重要的，回头再来关注他怎么实现。
对学习算法的方法总结
第一阶段：想法直观化，可以破坏程序性表达。做到感性认识，和本质理解。脑海中尽力想象样子。
第二阶段：从写代码的角度学习，想法把第一阶段脑海中的东西转化成用代码怎么写，怎么转化成数组，字典，比如快排的partion，直观想很简单，但代码写还没那么简单。比如kmp的next数组，感性认识（手工求）和代码写甚至就是两种方法了。
如果没有第一阶段，半年或者一年后基本就又忘了具体怎么做了。如果只有第一阶段，就不知道怎么写代码，也不容易很快分析出复杂度。两种阶段结合在一起才能形成完整、深刻的认识和理解。
.jpg)