此贴汇总已在力扣发布和计划发布的图论相关证明文章。

类别	文章	备注
最短路	Dijkstra算法正确性证明	数学归纳法 & 反证法
	Bellman-Ford及SPFA算法正确性证明(说明)	兼谈BF与SPFA，SPFA与BFM的关系
	Floyd算法正确性证明(说明)	从动态规划角度说明
最大流	最大流最小割定理证明	即FF方法正确性证明 FF: Ford-Fulkerson
	Edmonds-Karp算法复杂度证明
	Dinic算法复杂度证明
最小生成树	Prim算法正确性证明

---

yuki的其他文章如下，欢迎阅读指正！

如下所有文章同时也在我的 github 仓库 中维护。

文章	[发布时间] 字数/览/藏/赞 (~2022-10-20)
十大排序从入门到入赘 🔥🔥🔥	[20220516] 2.5万字/64.8k览/3.7k藏/937赞
二分查找从入门到入睡 🔥🔥🔥	[20220509] 2.3万字/38.4k览/2.1k藏/503赞
并查集从入门到出门 🔥🔥	[20220514] 1.2万字/17.9k览/1.0k藏/321赞
图论算法从入门到放下 🔥🔥	[20220617] 5.6万字/19.9k览/1.3k藏/365赞
树ADT系列 (预计13篇)	系列文章，连载中
3. 二叉查找树	[20220801] 5千字
4. AVL树	[20220817] 5千字
5. splay树	[20220817] 5千字
6. 红黑树从入门到看开 🔥🤯🤯🤯	[20220915] 3万字/5.3k览/269藏/72赞
10. 树状数组从入门到下车 🔥🤯	[20220722] 1.4万字/5.8k览/196藏/72赞
11. 线段树从入门到急停 🔥🤯	[20220726] 2.5万字/8.7k览/481藏/138赞
图论相关证明系列	系列文章
1. Dijkstra正确性证明 🤯	[20220531]
2. Prim正确性证明 🤯	[20220919]
3. Bellman-Ford及SPFA正确性证明	[20220602]
4. Floyd正确性证明	[20220602]
5. 最大流最小割定理证明 🤯🤯	[20220719]
6. Edmonds-Karp复杂度证明 🤯🤯	[20220515]
7. Dinic复杂度证明 🤯🤯	[20220531]

以下是原帖。

---

前一阵看图论的时候，搞了一些算法正确性证明，复杂度证明，费时甚巨。想了解下大家对这些证明是否感兴趣，在刷题阶段如何取舍。大家会对这类话题感兴趣吗？后续其实有点想在力扣上写一个系列文章（毕竟费了好大力气😅），感觉可能没人看。。。🤔🤔🤔