最短路

[Ir1d]

https://oi-wiki.org/graph/shortest-path/

[14w10]

太强了

[GitPinkRabbit]

Floyd 也可以判断负环是否存在，Johnson 用了 Bellman-Ford 当然也可以判断负环是否存在，请有关人员修改一下。

[Enter-tainer]

@GitPinkRabbit 可以开一个 issue 或者开一个 pr 吗

[GitPinkRabbit]

@Enter-tainer
@GitPinkRabbit 可以开一个 issue 或者开一个 pr 吗

怠惰~ （其实是因为不熟悉 github，能让其它人帮忙吗）

[StudyingFather]

@Enter-tainer
@GitPinkRabbit 可以开一个 issue 或者开一个 pr 吗

怠惰~ （其实是因为不熟悉 github，能让其它人帮忙吗）

那我来修吧（

[WYCTSTF]

我还是认为不能判定从源点出发找到负环 他本身是可以找的 这与“严谨”无关啊 我分析都给了 这也不是多难理解 多么需要严格分析的内容 洛谷记录也都贴出来了

要不再找个审核（比方说Menci）来看看吧

[WYCTSTF]

指定的点出发找负环 是做不了的 我的总意见只有这一点

[GitPinkRabbit]

我认为 @StudyingFather 的修改意见比较符合原意，即单源最短路模型本身。任何加超级源 / 初始虚拟 dis 值等理解方式可以算是把原问题复杂化了（尽管新问题只是点数为 n+1 的原问题的特例）。当然这两种理解方式都不算错。

进一步，我认为 “Bellman–Ford” 作为算法而言，能 “仅求源点能到达的点中有没有负环” 在功能上似乎是优于 “仅能求全局负环” 的（当然这两者也等价）。我倾向于前者。

[WYCTSTF]

进一步，我认为 “Bellman–Ford” 作为算法而言，能 “仅求源点能到达的点中有没有负环” 在功能上似乎是优于 “仅能求全局负环” 的（当然这两者也等价）。我倾向于前者。

嗯，我刚刚忽略了SF代码修改的pr，如果加上那个判断的话，写法是对的，这样改确实更简洁。

[zeta-y]

Johnson全源最短路的例子错了，那个图其实是一个负环，1-2没有最短路

[minghu6]

最小生成树和这里都提到了Fib堆，这里稍微讲一下，由于完整的Fib依赖链表结构（这种算法就是靠指针跳来跳去来实现看起来很优的理论时间复杂度），它有三大优点：

1. 代码行数多
2. 实现容易出错
3. 在大缓存的CPU架构下实际表现特别差

而相对地，二叉堆不仅实现简单，而且可以在一块儿连续内存上实现， 不仅简单而且非常快

[laozhu1234]

dijikstra的正确性证明翻译得有些难懂, 我找到一个不错的证明,可能就是来源: https://www.cs.auckland.ac.nz/software/AlgAnim/dij-proof.html

[xiao-ming-hub]

我觉得这个解释也很直观: https://zhuanlan.zhihu.com/p/570932634

[Pinghigh]

貌似是一种新的带负边权单源最短路算法

[sxshm01]

讲解的十分详细，点赞！！！

[luogu715948]

棒棒的

[ShawxingKwok]

Dijkstra 算法的推导可以看这里 https://leetcode.cn/circle/discuss/sgAKV4/

[2huker]

Floyd 传递闭包那里能不能写得详细些，直接用 bitset 优化看不懂欸/kk 可能是我太弱了

[yellow-mt]

关于spfa,它。。。。

[Po00iu6]

死了

[Po00iu6]

果然，还是来这里看得好理解！