引言：学习图论，好痛的领悟
这段时间在重新学习图论，最让我头疼的点是：我明明以前在不同的时间点学相关算法了，当时也感觉搞懂了，但是每次刷题，或者重新打开算法导论的相关章节，依然像是初学一样。
比如前几天的leetcode每日一题（2022年11月26日）：882. 细分图中可到达到的节点，看第一眼就知道需要用Dijkstra算法，但是怎么也写不出来。可明明天几前，我还在B站刷到Dijkstra相关的动画图解视频，觉得很轻松呀🤣。
这真的让人泄气。
仔细分析原因，无非是三点：
- 急功近利。每次都是恨不得一天之内掌握全部细节，翻开《算法导论》相关章节，仿若天书，读的很痛苦；于是翻开《大话数据结构》这本通俗读物看一遍，又发现讲的废话太多；于是又打B站，刷几个动画形式的讲解视频，惊呼"我去，这么简单"，仿佛登上了巅峰，宇宙都在我手里了。然后，过几天，全忘。
- 没有透彻地、系统地理解相关原理。表面上书看懂了，视频也看懂了，但是如果用自己的话复述相关算法，会发现根本做不到。如果过一段时间，甚至会发现图论的那几个算法，长得和亲兄弟似的，傻傻分不清。书也好，视频也好，都是用别人的语言表达的，特别是《算法导论》追求形式化和严谨性，理解它是一回事，将它其纳入自己的知识体系是另一回事。这也是我写这个公众号的原因之一：用自己的语言记录学习过程，加深印象。
- 缺乏及时、足量的练习。纸上学来终觉浅，算法最终还是要多敲多练，才能掌握。
比如最近这次重新学习，尽管我2022年11月27日，周六，昨夜到凌晨三点，把《算法导论》第三版《第24章：单源最短路经》，又又又又啃了一遍，当时觉得自己这次是真的掌握了，然后满意地睡了。
结果第二天醒来，大脑又空白了🤣。
尝试自己的话，复述一遍Dijkstra算法
逼自己复述的过程，是相当痛苦的，但是值得。
Dijsktra算法，只适用于边的权重非负的图。
对图的每个顶点v，都附加d和π两个额外属性。
d表示起点r到v的预估最短路径，算法开始前，将d设为正无穷大∞，算法执行过程中，d会不断减小，当算法停止时，d就是r到v的最短路径。π表示某条最短路径中，节点v的前驱节点，算法开始前，将π初始化为空节点；算法结束后，根据π，可以还原出这条路径；如果不需要还原路径，算法可以忽略π。
对起始点r，设置r.d = 0，r.π = r，也就是r到r的预估最短路径是0。将所有节点推入一个最小优先队列pq中，pq按照顶点的d属性来判断优先级，此时队列最小元素为r。
只要队列不为空，就反复进行如下迭代：将优先队列pq中的最小元素minV推出，遍历minV的每个相邻顶点u，对边(minV, u)进行松弛操作。
所谓松弛，就是如果u.d > minV.d + w(minV, u)，则更新u.d为minV.d + w(minV, u)，更新u.π = minV，其中w(minV, u)代表边的权重。松弛的原理很好理解，每发现一条更小的预估最短路径，则更新之。
队列为空后，算法停止。
以上是我自己的复述，对应原书中下图的伪代码：
一些细节
细节是魔鬼。这一小节，有助于加深对Dijkstra算法的理解，但初学的读者可以先跳过，对这个算法有整体印象后再回到此处。
和常见的Dijkstra算法讲解相比，比如B站王树森大神的版本，可以发现《算法导论》的表述有所不同：算法开始时，顶点是一次性全部被推入优先队列的，并且一旦出队列，后续也不会再次被推入队列。具体细节可以参考我昨天写的这篇：Dijkstra算法，从治愈到再住院丨老宋啃《算法导论》的笔记01。
Dijkstra算法，很容易让人联想到用广度优先遍历(bfs)法求解无权图最短路的问题，二者有不少相似之处。二者都会在某个顶点v出队列后，考察其所有的临接节点。
但是，bfs在遇到被访问过的节点时，会直接跳过，不会让其重复入队；而Dijkstra允许反复考察被访问过的节点，即便节点v已经被考察过，依然需要更新其d（松弛操作），并在下一次循环中参与队列中元素最小值的竞争；在我昨天提供的那个变通版Dijkstra模板中，甚至允许同一个节点反复入队。
不用担心会因此陷入死循环，因为重复考察一个顶点v，只有存在多条边通向v时才会出现。所有顶点被考察的总次数，和图中边的总数恰好相等。
《算法导论》原书对Dijkstra的证明
《算法导论》这本书的特点，就是话多、书厚、证明多，读的时候像天书，好不容易一个字一个字地理解了，转头就忘。但是如果彻底理解了，会发现这本书就没那么厚了。此书对Dijkstra算法的证明，就是个典型的例子。下面的这一页纸，是我2022年11月27日那个周六晚上的噩梦：
读者可以先跳过这场噩梦。
我自己对Dijkstra算法的证明
总体思路，是使用数学归纳法和反证法。
证明之前，首先必须深入体会松弛操作：Dijkstra算法执行过程中，顶点的预估最短路径d，只可能从+∞逐渐减小，不可能一会减小，一会有增大。
可以发现，《算法导论》中的版本，一旦某个顶点出了队列，就不会再次入队了。换句话说，顶点v出队列的时候，起点r到v的最短路径，就尘埃落定了，恰好等于此时的d值。
于是证明关键，转换为：顶点v出队列时，不可能存在一条路径p，比顶点此时的v.d更小。
算法执行过程中，顶点其实被分成两组，一组是推出优先队列pq外面的，一组是pq之内的。标记队列外的为黑色节点，另一组为白色节点。起点r到黑色节点的最短路径，已经是被确定了的，黑色节点的d值不会再减小。而即将被推出队列的节点，就是白色节点中d值最小的那个。
数学归纳的第一步，是考察起始节点r。第一次出队列的节点必然是r，因为其r.d被初始化为0，而其他节点的值此时都是∞。显然，r到r的最短路径，就是0，结论成立。r被推出后，黑色节点组只有一个成员。
接下来，用反证法考察数学归纳法的归纳步。假设节点v正好要被推出队列，并假设此时的v.d，不是r到v的最短路径，而是存在一条更短的路径p；设这条路径p上，v的前一个节点为x。记p的长度为，于是有：
x不是黑色的，就是白色。分情况讨论：
- 假如
x是黑色的，那么x已经出队。x刚出队的时，v作为x的一个临接顶点，边(x, v)必然会被进行一次松弛操作，v.d与x.d+w(x,v)会被进行比较。由于松弛操作只会让d变小，不会变大，所以必然有。与式1矛盾。 - 假设
x是白色的，那么x必然队列中，有，否则v就不是最小队列的中的最小元素了，因为x比它还小。与式1矛盾。
所以，更短的p是不存在。得证。
结语
我这个证明思路，和《算法导论》原文不太一样，不过我觉的殊途同归。当然，因为我还比较菜，可能整个都是错的，欢迎指出。
写到这里，突然有点感想。写只给自己看的东西，和写公开文章，区别真的很大。
我阅读《算法导论》的时候，每当费力啃完一个章节后，会感觉一个简单的意思，作者要写一整页甚至好几页纸，很想吐槽。但是自己写公众号，发现写算法类文章，准确表达一个意思真的是很困难的。
甚至于，每敲一个字，都会反复纠结：写多了，会担心自己写的太啰嗦、太口水，读者会厌烦；写少了，又害怕没表达清楚，读者会困惑。
写完后，还得反复检查有没有错漏，避免翻车。
本来，我自己写读书笔记，或者在leetcode里写刷题笔记，感觉很简单，一小会就能码出上千字，反正都是给自己看的🤣。
所以，写作这条路，道阻且长，还得修炼，欢迎关注（微信搜索「程序员老宋」）。
