最短路

作者： 作者的头像   h._ ,  2023-06-26 09:55:24 ,  所有人可见 ,  阅读 162

1


单源最短路：
①所有边权都是正数：
1.朴素Djikstr算法：O(n^2)
2.堆优化版Djikstra算法：O(mlogn)

②存在负权边：
1.Bellman-ford: O(nm)
2.SPFA: 一般O(m), 最坏O(nm)

多源汇最短路：(起点和终点都不确定)
Floyd: O(n^3)

0 评论

1024
x