各种最短路算法的适用情况及时间复杂度如下:
存在负权边,或者判定负环,推荐用SPFA算法。对最短路的边数存在限制,则只能使用Bellman Ford算法。
最小生成树的算法及其时间复杂度如下:
堆优化版的prim算法几乎不会用到,Kruskal算法的时间复杂度与其近似,思路与代码实现都更优。
二分图的相关算法及时间复杂度如下: