MENU

Catalog

    单源最短路径(4):总结

    March 30, 2018 • 文章

    

    系列文章目录

    单源最短路径(1):Dijkstra算法
    单源最短路径(2):Bellman_Ford算法
    单源最短路径(3):SPFA算法
    单源最短路径(4):总结

    前面我们说,Dijkstra算法不能处理存在负权回路的图,其实,如果一个图仅仅存在负权边,那么Dijkstra算法也可能是无法处理的,例如下图,若A作为源点,在第一轮循环后,B被标记数组标记,但我们发现在第二轮循环中,B还可以通过C点继续进行更新。

    Dijkstra算法在实际工程项目中可以说是经常碰到的,主要是因为其高效又稳定的时间复杂度。当使用二叉堆作优先队列时,时间复杂度为$O((m+n)logn)$。

    Bellman_Ford算法可以处理存在负权边的图,也可以判断有无负权回路。它的时间复杂度很稳定,但同时也很高,为$O(nm)$,在一些实际项目中往往无法让人接受。

    SPFA算法和Bellman_Ford算法一样,既可以处理存在负权边的图,也可以判断有无负权回路。但与Dijkstra和Bellman_Ford算法都不同的是,它的时间复杂度很不稳定,最佳时间复杂度为$O(n)$,最差时间复杂度为$O(n^3)$。

    总结起来就是下面的表格:

    时间复杂度是否可以处理负权边是否可以判断负权回路
    Dijkstra算法$O((m+n)logn)$不可以不可以
    Bellman_Ford算法$O(nm)$可以可以
    SPFA算法$[O(n),O(n^3)]$可以可以
    Archives QR Code Tip
    QR Code for this page
    Tipping QR Code
    Leave a Comment

    已有 1 条评论
    1. @(吐舌)沙发~Dijkstra大法好!