圖論中幾種最短路算法性能比較—— Floyd,Dijkstra,SPFA,Bellman-Ford及它們的優(yōu)化

目錄

  • Floyd

    • 鄰接表
      • 鄰接表

  • Dijkstra

    • 隊列優(yōu)化

  • Bellman-Ford 與 SPFA

? - 負環(huán)判斷

  • 比較結論

  • 其他

??
?
?
?
?

1. Floyd

基于動態(tài)規(guī)劃
復雜度 O(n^3)
求出任意兩點最短路徑
通過每一點松弛所有其他路徑
遞推式map[ i ][ j ] = min ( map[ i ][ j ], map[ i ][ k ] + map[ k ][ j ] )
關鍵代碼

    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                map[i][j] = min(map[i][j], map[i][k] + map[k][j]);

2. Dijkstra

單源最短路徑
基于貪心(在路徑值無負權情況下)
復雜度 O(N^2) （鄰接矩陣）adjacency matrix
復雜度 O((M+N)logN) （鄰接表）adjacency list
當圖中路徑較少時（m < n^2）(稀疏圖)，使用鄰接表更優(yōu)
尋找dis[ ]中最小值的時候如果用C++ STL中的優(yōu)先隊列priority_queue可以優(yōu)化常數(shù)。
本文主要研究基于C語言的最短路算法，暫不占用過多篇幅實現(xiàn)二叉堆排序

思路: 求A點到所有其他點的最短路徑。重復以下步驟 : 找出離A最近的點B，通過B點對其他點進行松弛(當前A,B點間距肯定已經(jīng)是最短的了，因為它無法通過其他點進行松弛)(無負權)。

鄰接表

鄰接表的存儲
類似鏈表, 這里通過結構體實現(xiàn), 假設路徑數(shù)量 m<1000, 結點數(shù) n<300

typedef struct node{
    int u, v, w;                     //使用該結構體存放讀取的路徑
}node;                               //u起始點 v終點 w路徑權值
node road[1000];

再定義兩個數(shù)組來模擬鏈表
first[]的鍵名表示結點， 鍵值表示路徑編號
next[]的鍵名表示路徑編號， 鍵值表示路徑編號
它們一般定義為全局數(shù)組，初始值為0。

int first[300];//first[u]存放以u號結點為起始點的首條路徑(讀取時反向存放)
               //所以該數(shù)組空間應該大于等于結點數(shù) n
int next[1000];//next[i]存放i號路徑的下一條路徑,這兩條路徑起始點相同
               //所以該數(shù)組空間應該大于等于邊數(shù) m

讀取路徑時如何存放

cin >> road[i].u >> road[i].v >> road[i].w; //讀第i條路徑的起始點,終點,權值
next[i] = first[road[i].u];
first[road[i].u] = i;

這里是反向存放，把最后讀取的邊當作第一條，在first[ ]中。
鄰接表存放有點繞，嘗試解釋一下
讀第i條邊時的處理方法：
first[road[i].u]存放的是以road[i].u這個結點為起始點的上一條路徑的路徑編號(不妨記為i')(如果現(xiàn)在讀取的這條邊是以該結點為起始點的第一條路徑,那么由于該數(shù)組是全局數(shù)組，first[road[i].u]的值為0,即i'==0)?，F(xiàn)在把這條路徑的編號賦給next[i]，表示路徑i的下一條路徑為i', 然后把i賦給first[road[i].u]。

鄰接表的遍歷

當要遍歷以結點u為起始點的路徑時，從first[u]出發(fā),first[u]存放了第一條邊 ，然后不斷獲得 next[邊號]即可

int head = first[u];
while(head != 0) 
{
  --- 對該邊進行操作 ---
  head = next[head];
}

Dijkstra(鄰接表)核心代碼

for(int i=1; i<n; i++)
    {
        int min_w = 0x7fffffff;                   //尋找剩余結點中離目標結點(1號結點)最近的
        int tar = 0;                              //結點編號，初始化為0
        for(int j=2; j<=n; j++)                  //如果找完一趟后還是0，代表剩下的節(jié)點都不能與1相連了
        {
            if(!book[j] && dis[j] < min_w)        //book[j]為 1代表已經(jīng)利用過
            {
                tar = j;
                min_w = dis[j];
            }
        }
        if(tar)
        {
            book[tar] = 1;
            int head = first[tar];
            while(head)
            {
                int nv = road[head].v;
                int nw = road[head].w;
                if(dis[nv] > nw + dis[tar])
                    dis[nv] = nw + dis[tar];
                head = last[head];
            }
        }
        else
            break;
    }

兩種方法的核心代碼比較類似，變量代表的含義基本相同

Dijkstra(鄰接矩陣)核心代碼

 for(int i=1; i<n; i++)
    {
        int min_w = 0x7fffffff;
        int tar = 0;                         
        for(int j=2; j<=n; j++)
        {
            if(book[j] == 0 && map[1][j] < min_w)
            {
                tar = j;
                min_w = map[1][j];
            }
        }
        book[tar] = 1;
        if(!tar) 
            break;
        for(int j=2; j<=n; j++)
        {
            if(book[j] == 0)
            {
                if(map[1][j] > map[1][tar] + map[tar][j])
                {
                    map[1][j] = map[1][tar] + map[tar][j];
                }
            }
        }
    }

3. Bellman-Ford

該算法的思路和代碼量都比較簡短。
可以是看作犧牲一部分復雜度Dijkstra的基礎上能夠判斷處理負權，判斷負權環(huán)。
對有一張有n個點，m條邊的有向圖, 用數(shù)組dis[ ]保存源點到各點的最短距離，可以通過對邊進行 n - 1 次的遍歷，當其滿足dis[v] > dis[u] + w的時候，就對其進行松弛更新操作，重復n-1次以后就能得到答案，如果n-1次以后還能繼續(xù)更新，則可以判斷圖中出現(xiàn)了負權環(huán)。

for(int i=1; i<n; i++)             //最多進行 n-1 次
{
    bool checked = 0;    //用checked判斷這次循環(huán)有無進行松弛操作，若無，則直接退出    
    for(int j=1; j<=m; j++)      //使用每條邊嘗試松弛
    {
        if(dis[road[j].v] > dis[road[j].u] + road[j].w)
        {
            checked = 1;
            dis[road[j].v] = dis[road[j].u] + road[j].w;
        }
    }
    if(!checked)
        break;
}

4.SPFA

SPFA在Bellman-Ford的基礎上加以改進
再Bellman-Ford算法中一方面每次循環(huán)不需要對所有邊進行松弛判斷，只需要對上次松弛操作時成功松弛的結點延伸出的邊再進行松弛判斷。
因此我們加上隊列，讓成功松弛的結點進入隊列。(類似于廣搜的思想。 但由于在存在 n 個結點的有向圖中, 對于任意結點 i ，在 n-1 次操作之前，即使該結點被成功松弛，亦不一定為最短路徑，可能在后面又被更新。所以一個結點可能進入該隊列不止一次。這一點區(qū)別于普通BFS。
由于是針對每個結點的操作，在稀疏圖中(這也是大部分我們所遇到的情況)使用鄰接表較方便

SPFA代碼(放上全文,一方面SPFA是應用得最多的單源最短路算法,另一方面之前寫的時候遇到了點小bug,調(diào)試了好久, 長個記性)
#include<iostream>
#include<cstring>
using namespace std;
int n, m;                  // n<=100, m<=1000
typedef struct node{
    int u, v, w;
}node;
node road[1000];
int first_road[100], next_road[1000];    //鄰接表
int queue[1000];                  //實現(xiàn)隊列
int times[100];                   //每個點進入隊列次數(shù)
bool book[1000];  
int dis[100];     
bool flag;                        //判斷負環(huán)               
int main()
{
    cin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        cin >> road[i].u >> road[i].v >> road[i].w;
        next_road[i] = first_road[road[i].u];
        first_road[road[i].u] = i;
    }
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    int head = 0, tail = 1;
    queue[head] = 1;
    book[1] = 1;
    times[1]++;
    while(head < tail)
    {
        int now = queue[head];            //結點
        int bian = first_road[now];       //遍歷該結點的路徑
        while(bian)
        {
            if(dis[road[bian].v] > dis[road[bian].u] + road[bian].w)
            {
                dis[road[bian].v] = dis[road[bian].u] + road[bian].w;
                int next_node = road[bian].v;
                if(book[next_node] == 0)
                {
                    if(times[next_node] >= n)
                    {
                        flag = 1;
                        break;
                    }
                    book[next_node] = 1;
                    queue[tail++] = next_node;
                    times[next_node]++;
                }
            }
            bian = next_road[bian];
        }
        book[queue[head]] = 0;
        head++;
        if(flag)
            break;
    }
    if(flag)
        cout << "存在負環(huán)";
    else
        for(int i=1; i<=n; i++)
            cout << dis[i] << ' ';
    cout << endl;
    return 0;
}

負環(huán)判斷

Bellmam-Ford和SPFA算法都可以進行圖的負環(huán)判斷。
對于Bellman-Ford：第n次松弛操作還能成功更新dis[ ]的值，則存在負環(huán)
對于SPFA： 如果一個點進入了隊列n次，則存在負環(huán)

結論

算法 簡述 時間復雜度 負權和負權回路
Floyd 動態(tài)規(guī)劃 O(N^3) 可以處理負權,不能判斷負權回路
Dijkstra 貪心,對點處理 O((M+N)logN) 什么都不能
Bellman-Ford 對邊處理 O(MN) 可以處理負權,判斷負權回路
SPFA 優(yōu)化的Bellman O(MN) 可以處理負權,判斷負權回路

?

遇到的一些問題:

1. memset的原理

memset是為char[ ]設計，處理字節(jié) , 即 memset(a,0xff,sizeof(a)) , 將a的每一個字節(jié)弄成 ff .
當我們對int[ ]使用memset時，int 4個字節(jié) 每一個字節(jié)都會是 ff。
使用建議：

  1. 0x7f 每個字節(jié)第一位位0后面全是1，這是用memset讓int能達到的最大值
  2. 0x3f 3f+3f=7e 達到 無窮大+無窮大=無窮大的效果 計算時避免溢出 優(yōu)于第一種

2. 生成隨機數(shù)據(jù)

在C語言中，我們一般使用 <stdlib.h> 頭文件中的 rand() 函數(shù)來生成隨機數(shù)，它的用法為：int rand (void);
rand() 會隨機生成一個位于 0 ~ RAND_MAX 之間的整數(shù)。
RAND_MAX 是 <stdlib.h> 頭文件中的一個宏，它用來指明 rand() 所能返回的隨機數(shù)的最大值。C語言標準并沒有規(guī)定 RAND_MAX 的具體數(shù)值，只是規(guī)定它的值至少為 32767。在實際編程中，我們也不需要知道 RAND_MAX 的具體值，把它當做一個很大的數(shù)來對待即可。
srand((unsigned)time(NULL));重新播種

最后編輯于 ：
?著作權歸作者所有,轉載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

友情鏈接更多精彩內(nèi)容