会撒娇羽毛

文章
5
资源
0
加入时间
2年10月17天

最短路径算法复杂度总结

Dijkstra:O(n2)适用于权值为非负的图的单源最短路径,用斐波那契堆的复杂度O(E+VlgV), BellmanFord:适用于权值有负值的图的单源最短路径,并且能够检测负圈,复杂度O(VE) SPFA:适用于权值有负值,且没有负圈的图的单源最短路径,论文中的复杂度O(kE),k为每个节点进入Queue的次数,且k一般<=2,但此处的复杂度证明是有问题的,其实SPFA的最坏情况应该是O(