【OI之路】03图论算法-3最短路之Dijkstra

Dijkstra
在无负权的图中,找最短路
可防止被卡边(spfa容易被卡)
时间复杂度相对没那么玄学,比较稳定(如果慢,那就真的慢)

简单讲讲

dijkstra算法基于贪心思想,每次找最小的dist来更新
这是因为,当边长都是非负数的时候,全局最小的那个dist显然不会再被更新,所以已经是最短路径
堆优化就是在找最小的dist的时候,用堆维护,时间复杂度从 $O(n^2)$ 变成 $O(mlogn)$

总结

参考:Here

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/5c8c.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%