ACM算法竞赛——最短路知识结构总结

n代表点数 m代表边数

最短路

1.单源最短路

····1.1所有边权都是正数

············1.1.1朴素dijkstra算法 O(n^2) 适合稠密图

············1.1.2堆优化版dijkstra算法O(mlogn) 适合稀疏图

····1.2存在负边权

············1.2.1 Bellman-Ford O(mn) (经过的边数小于等于k)

············1.2.2 SPFA 一般：O(m) 线性 最坏:O（nm）

2.多源汇最短路

····2.1 Floyd算法 O(n^3)

最短路问题难点在于：建图