圖的最短路徑

• 迪杰斯特拉算法
• 貝爾曼-福特算法
• 弗洛伊德算法
• SPFA算法(中國西南交通大學段凡丁發(fā)明)

最短路徑問題分為兩類马昙，一大類是求一個頂點到其余各頂點的最短路徑問題玻靡，另一大類是求各個頂點間最短路徑問題幔妨。

迪杰斯特拉

迪杰斯特拉算法就是求解一個點到其余各點的最短路徑算法，無向圖帶權(quán)圖和有向帶權(quán)圖都適用僻族。缺點是不適用權(quán)值為負數(shù)的圖(后面會講解原因)

算法步驟

1. 初始的點為起點车遂，我們用s集合存儲已經(jīng)確定最短路徑的點的集合淤齐，那么s={v},起點加入。其余各個點到v點的權(quán)值存儲在dis數(shù)組里，不是直接連接的點距離都是無窮大
2. 從dis數(shù)組選出一個頂點u碘裕，這個點u到v點距離最小，把u加入s集合表示u已經(jīng)確定了最短路徑
3. 以點u為中介點攒钳，將除了s集合存儲的點以外的其余點逐個判斷帮孔，如果某個點x存在dis[u]+u點到x點距離<dis[x],就更新x的路徑。
4. 重復(fù)2不撑，3步驟文兢，直到s集合包含了所有點。

我們還是直接上圖看完整流程

tree24.jpg

首先我們先準備幾個輔助數(shù)組,我們假設(shè)從點A為起點焕檬，找其它點到點A的最短路徑

我來說明下姆坚，這幾個數(shù)組的作用
權(quán)重數(shù)組存儲每個點到A點的最短距離

前驅(qū)數(shù)組存儲的是每個點前驅(qū)點下標，例如B點前驅(qū)是0实愚，表示B和A連接,前驅(qū)是A

標記數(shù)組存儲的是當前點是否已經(jīng)找到了最短路徑兼呵。

接下來我們準備工作做好了，開始干活了!

1.按照算法步驟腊敲，找出沒被標記點中權(quán)重最小的點击喂，我們找到了D點，將D點標記為1碰辅，表示D點以確認最短路徑懂昂，然后以D點為中介判斷未標記點，首先來到了B點没宾，權(quán)重數(shù)組中B對應(yīng)的是4凌彬，根據(jù)算法步驟3，我們計算出權(quán)重數(shù)組D+BD距離2+1=3 < 4(4就是權(quán)重數(shù)組B的值)所以B當前有一條路徑比之前近榕吼，所以修改了B點對應(yīng)的權(quán)重為3饿序，同時更新它的前驅(qū)是D的下標。意思就是經(jīng)過D點到B羹蚣，更加近原探。同理繼續(xù)看下一個未被標記的點C，繼續(xù)計算權(quán)重數(shù)組D+CD距離 2+1=3 <∞,拿C點也要修改權(quán)重為3，同時更新C點前驅(qū)是D咽弦，繼續(xù)看下一個未被標記點E徒蟆，發(fā)現(xiàn)權(quán)重數(shù)組D+DE=9<∞,所以也修改E點權(quán)重為9，同步更新它的前驅(qū)是D型型。如下表就是第一次更新后的結(jié)果

2.找出當前表中未標記點權(quán)重最小的段审，來到了B點和C點，我們選擇B(隨便哪一個都行)將B標記為1闹蒜，接著逐個判斷未被標記點寺枉，首先是C，權(quán)重數(shù)組B+BC距離 3+4 >3所以不修改绷落。又來到了E姥闪，權(quán)重數(shù)組B+BE 3+∞ >9 ,也不修改，如下表就是第二次更新的結(jié)果

3.找出當前表中未被標價點權(quán)重最小的是C點砌烁，將C點標記為1筐喳，然后判斷未被標記的，只剩E點函喉，權(quán)重數(shù)組C+CE距離 3+3<9 所以修改E點權(quán)重是6避归，更行E點前驅(qū)是C的下標，如下表就是第三次更新的結(jié)果

4.找出最小管呵，只剩下E點梳毙，直接標記E點是1，結(jié)束撇寞。

有了上面一張表顿天，我們就可以求出每個點到A點的最短路徑了，我舉兩個點例子蔑担。

首先是點B牌废，根據(jù)前驅(qū)下標進行尋找，B前驅(qū)下標是3啤握，對應(yīng)點D鸟缕，所以B點前驅(qū)是D，接著D點前驅(qū)下標是0排抬，對應(yīng)點A懂从，接著A點前驅(qū)下標是-1，退出蹲蒲。所以整個逆序路徑就是B-D-A

接著看E點番甩，前驅(qū)下標是2就是C點，C點前驅(qū)是3是D點届搁，D點前驅(qū)下標是0缘薛，是A點窍育，A點前驅(qū)是-1，退出,整個逆序路徑是E-C-D-A

//迪杰斯特拉算法
void Dijkstra(struct MGraph *g, char obj)
{
    int *temp, *dis, *pre,index,min,k;
    temp = (int*)malloc(sizeof(int) * g->numVretexes);
    dis = (int*)malloc(sizeof(int) * g->numVretexes);
    pre = (int*)malloc(sizeof(int) * g->numVretexes);
    //找出源節(jié)點的位置
    for (int i = 0; i < g->numVretexes; i++)
    {
        if (g->vetex[i] == obj)
        {
            index = i;
            break;
        }
    }
    //初始化輔助數(shù)組
    for (int i = 0; i < g->numVretexes; i++)
    {
        temp[i] = 0;
        pre[i] = -1;
        dis[i] = g->data[index][i];
    }
    temp[index] = 1;
    for (int i = 1; i < g->numVretexes; i++)
    {
        min = MAX;
        //找出當前dis存儲最小的下標
        for (int j = 0; j < g->numVretexes; j++)
        {
            if (temp[j] == 0 && g->data[index][j] < min)
            {
                min = g->data[index][j];
                k = j;//標記最小值的位置
            }
        }
        temp[k] = 1;
        index = k;
        //從該點開始宴胧，逐個判斷并修改dis數(shù)組
        for (int j = 0; j < g->numVretexes; j++)
        {
            if (temp[j] == 0 && (g->data[k][j] + dis[k]) < dis[j])
            {
                dis[j] = g->data[k][j] + dis[k];
                pre[j] = k;
            }
        }
    }

    //dis數(shù)組就是源點到各個點的最短路徑
    for (int i = 0; i < g->numVretexes;i++)
    {
        printf("%c-->%c(%d)\n", obj, g->vetex[i], dis[i]);
    }
    printf("\n");
}

貝爾曼-福特

首先我們在這里回答下漱抓，為什么迪杰斯特拉算法不可以計算帶負權(quán)的圖。我們直接舉例子分析吧

tree25.jpg

看這個圖恕齐，存在帶負權(quán)的邊乞娄，現(xiàn)在我們按照迪杰斯特拉算法去求解A點到其它點的最短路徑問題。

首先選出權(quán)重最小的是點C显歧，標記點C是1仪或，然后判斷未被標記點D 權(quán)重數(shù)組C+CB距離<權(quán)重數(shù)組B,所以修改點B對應(yīng)的權(quán)重是0，且更行它的前驅(qū)是2.接著只剩下點B追迟，標記它溶其，完成骚腥。最終的表如下

根據(jù)表發(fā)現(xiàn)敦间，A點到C點的最短距離是2，可是我們一眼可以發(fā)現(xiàn)束铭，從A到B再到C的距離是1廓块，所以迪杰斯特拉不成立啊。什么原因契沫？仔細看迪杰斯特拉算法的特性带猴。它每次都找出當前權(quán)重數(shù)組最小的，找到后懈万，就確認了這個點已經(jīng)是最近的拴清。可是如果后面其他邊可能會存在負數(shù)邊会通，會讓這個點距離目標點更近口予。講的有點繞，大家還是看圖分析吧涕侈。

貝爾曼-福特求解思路

為了能夠求解帶又負值的單原最短路徑問題沪停，貝爾曼-福特從原點逐次繞過其它點，通過松弛操作以達到縮短終點的最短路徑方法裳涛。

什么是松弛操作木张？我舉個例子，假設(shè)權(quán)重數(shù)組A存儲的是3,權(quán)重數(shù)組B存儲的是10端三，而點A到B有一條邊距離是2舷礼，那么你說是不是應(yīng)該修改權(quán)重數(shù)組B存儲的值了，先到達A點郊闯，再到達點B的距離僅僅是3+2=5,表示路過B到達A妻献，比直接到A的路徑短浮声，修改A的權(quán)重是5。

1. 我們準備兩個數(shù)組旋奢，一個是path數(shù)組泳挥，就是前驅(qū)數(shù)組，存儲路徑的至朗，另一個就是dis數(shù)組屉符，存儲權(quán)重.將它們初始化，path數(shù)組全部初始化為-1锹引，dis數(shù)組全部初始為無窮大矗钟，并初始化原點的dis為0
2. 因為有n個點,所以最多有n-1條邊,所以需要執(zhí)行n-1次循環(huán)，每次循環(huán)都對每條邊進行松弛的判斷嫌变。

總結(jié)下,就是對于圖的每條邊,將每個點進行邊的松弛判斷,條件成立,修改dis數(shù)組

void Bellman_Ford(struct MGraph *g, char obj)
{
    int *dis, *pre,index,temp;
    dis = (int*)malloc(sizeof(int) *g->numVretexes);
    pre = (int*)malloc(sizeof(int) * g->numVretexes);
    //找出目標點位置
    for (int i = 0; i < g->numVretexes; i++)
    {
        if (g->vetex[i] == obj) {
            index = i;
            break;
        }
    }
    //初始化dis數(shù)組
    for (int i = 0; i < g->numVretexes; i++)
    {
        dis[i] = MAX;
        pre[i] = -1;
    }
    dis[index] = 0;
    for (int k = 1; k < g->numVretexes; k++)
    {
        for (int i = 0; i < g->numVretexes; i++)
        {
            for (int j = 0; j < g->numVretexes; j++)
            {
                if (j != index && i != j && g->data[i][j] != MAX)
                {
                    if (dis[i] + g->data[i][j] < dis[j])
                    {
                        dis[j] = dis[i] + g->data[i][j];
                        pre[j] = i;
                    }
                }
            }
        }
    }
    //經(jīng)過松弛后吨艇，如果還可以松弛，表示圖中存在負數(shù)權(quán)回路
    temp = 0;
    for (int i = 0; i < g->numVretexes; i++)
    {
        for (int j = 0; j < g->numVretexes; j++)
        {
            if (j != index && i != j && g->data[i][j] != MAX)
            {
                if (dis[i] + g->data[i][j] < dis[j])
                {
                    temp = 1;
                    printf_s("圖中存在負權(quán)回路\n");
                    return;
                }
            }
        }
    
    }
    //輸出dis數(shù)組
    for (int i = 0; i < g->numVretexes; i++)
    {
        printf_s("%d ", dis[i]);
    }
    
}

SPFA算法

SPFA算法是中國老師段丁凡老師發(fā)明的腾啥，用于求單源最短路徑問題的負權(quán)值問題东涡。不過不久被國際某某組織認定其論文的證明是錯誤的，我猜測可能段大神倘待，算法是牛逼的疮跑，可能在證明自己算法疏忽了細節(jié)，不過這個并不會影響我們對段老師的傾佩凸舵。此算法的核心就是利用隊列去無限的逼近最優(yōu)解祖娘，算法的主題和廣度優(yōu)先遍歷算法大體一樣，不同于廣度優(yōu)先遍歷啊奄，出隊頂點時渐苏，這個點還有可能再次入隊。

吐槽下菇夸，我按照算法思路寫出兩類代碼(網(wǎng)上算法步驟分為兩派)去和網(wǎng)上大佬們對比琼富，發(fā)現(xiàn)網(wǎng)上各種代碼的百分之99都是存在嚴重問題的，因為峻仇，它們對于這個SPFA的約束問題沒搞清楚公黑。也可能是老師當年沒完善吧，假設(shè)圖中無負權(quán)回路摄咆，SPFA算法在求解帶負權(quán)的無向圖是不成立的凡蚜，在求解帶負權(quán)的有向圖是正確的。這個當時我電腦測試了自己的一個版本吭从，當時還不行朝蜘，又進行了手繪圖測試，發(fā)現(xiàn)帶負權(quán)的無向圖還是有BUG涩金。大家有空可以測試下谱醇。希望大佬指點暇仲。

算法描述

1. 初始化隊列，將源點入隊列副渴。設(shè)置輔助數(shù)組dis初始化為無窮大,數(shù)組temp初始化為0,數(shù)組path初始化為-1,其中dis數(shù)組存儲源點到其它點的距離奈附，temp數(shù)組存儲對應(yīng)點是否在隊列里，path數(shù)組存儲對應(yīng)到源點的最短路徑煮剧。(path和迪杰斯特拉的path原理一樣)斥滤，設(shè)置源點下標對應(yīng)的dis值為0(自己到自己的距離是0)，設(shè)置源點下標對應(yīng)的temp值為1(源點在隊列里)
2. 出隊一個點point,設(shè)置該點在temp數(shù)組的值是0(代表該點出隊列),遍歷其它所有點i勉盅，凡是存在(dis[i]>dis[point]+point到i的距離)佑颇，就修改點i的在dis數(shù)組的值是dis[point]+point到i的值，并將該點入隊列草娜，更新temp數(shù)組的i的值為1.更新path數(shù)組對用i的值是point(代表該點的前驅(qū)點是point)
3. 循環(huán)執(zhí)行步驟2挑胸，直到隊列為空。

舉例分析整個過程,我們假設(shè)A是源點(起點)

tree27.jpg

1.初始化隊列宰闰，dis數(shù)組茬贵，temp數(shù)組，path數(shù)組议蟆，讓源點A入隊列,修改A的temp是1闷沥，A的dis值是0，此時的數(shù)組情況和隊列情況如下圖

queue6.jpg

2.出隊列隊頭A咐容，更新temp[0]=0(出隊),并逐個與其它點判斷(松弛操作),首先是B，發(fā)現(xiàn)dis[1]>dis[0]+AB的距離,(此處的dis[1]和dis[0]對應(yīng)的就是點B蚂维，點A戳粒，我們用頂點下標代替點)所以修改dis[1] = dis[0]+AB = 6,入隊點B，更新temp[1] = 1,path[1] = 0,接著是點C,發(fā)現(xiàn)dis[2]>dis[0]+AC虫啥，于是修改dis[2] = dis[0]+AC=-1,入隊點C蔚约，更新path[2] = 0,temp[2] = 1,最后來到了點D,發(fā)現(xiàn)dis[3]<dis[0]+AD,不修改.更新后的情況如下圖

queue7.jpg

3.出隊隊頭B，更新temp[1] = 0,逐個判斷與其它點涂籽，首先是A苹祟，dis[0]<dis[1]+BA不修改,接著是點C，dis[2]<dis[1]+BC,不修改评雌，接著是點D树枫，dis[3]>dis[1]+BD,修改dis[3]=dis[1]+BD=4,發(fā)現(xiàn)D未在隊列，讓D入隊景东，修改path[3]=1,temp[3]=1砂轻。更新后的如下圖

queue8.jpg

4.出隊隊頭C，更新temp[2]=0,逐個點判斷斤吐，首先是A搔涝，dis[0]<dis[2]+CA厨喂，不修改，接著是B庄呈，dis[1]<dis[2]+CB,不修改蜕煌，最后是點D，dis[3]>dis[2]+CD,修該dis[3]=dis[2]+CD=3,發(fā)現(xiàn)D在隊列里诬留，更新path[3] = 2幌绍。更新后的如下圖

queue9.jpg

5.出隊隊頭D，更新temp[3]=0,逐個點判斷故响，首先A是源點傀广，dis[0]<dis[3]+DA。接著B彩届，dis[1]<dis[3]+DB,接著是點C伪冰，dis[2]<dis[3]+DC,都不修改。此時隊列空樟蠕，退出更新后的如下圖贮聂。

queue10.jpg

此時的數(shù)組就是點A到其它點的最短距離和最短路徑了。path數(shù)組存儲的時路徑寨辩，看查看方式和迪杰斯特拉一樣吓懈，我們舉一個例子。AD的最短距離靡狞，我們查看dis數(shù)組dis[3] = 3耻警。
AD的最短路徑是path[3]=2,中間點是2,path[2]=0,中間點是0，path[0]=-1,沒點了甸怕。
所以AD的最短路徑就是A-C-D

代碼

void SPFA(struct MGraph *g, char obj)
{
    int index,i,*queue,*visit,*dis,*path,front,rear,top;
    queue = (int*)malloc(sizeof(int)*100);//防止隊列溢出(此處的隊列非循環(huán)隊列)
    visit = (int*)malloc(sizeof(int)*g->numVretexes);
    dis = (int*)malloc(sizeof(int)*g->numVretexes);
    path = (int*)malloc(sizeof(int)*g->numVretexes);
    //1.找出源點
    for (i = 0; i < g->numVretexes; i++)
    {
        if (g->vetex[i] == obj)
        {
            index = i;
        }
    }
    //2:初始化隊列,輔助數(shù)組
    for (i = 0; i < g->numVretexes; i++)
    {
        visit[i] = 0;
        dis[i] = MAX;
        path[i] = -1;
    }
    front = rear = 0;
    queue[rear++] = index;
    visit[index] = 1;
    dis[index] = 0;
    while (rear != front)//隊列空結(jié)束
    {
        top = queue[front++];
        visit[top] = 0;
        for (i = 0; i < g->numVretexes; i++)
        {
            if (i != top)
            {
                if (dis[i] > (dis[top] + g->data[top][i]))
                {
                    dis[i] = dis[top] + g->data[top][i];
                    path[i] = top;
                    if (visit[i] == 0)//沒在隊列里,入隊
                    {
                        queue[rear++] = i;
                        visit[i] = 1;
                    }
                }
            }
        }
    }
    //輸出最端距離和路徑
    for (i = 0; i < g->numVretexes; i++)
    {
        if (i != index)
        {
            printf_s("%c-->%c(%d)\n", g->vetex[index], g->vetex[i], dis[i]);
        }
    }
}

弗洛伊德算法

弗洛伊德算法是求圖中每個頂點之間的最短路徑算法甘穿，它的思想是利用動態(tài)規(guī)劃去得到問題的解。理解起來就是對圖中所有兩個頂點對梢杭，依次采取松弛操作温兼，找到最優(yōu)解。

算法描述

1. 首先準備兩個二維數(shù)組dis和path,dis數(shù)組存儲圖中兩個點的距離武契，path數(shù)組存儲兩個點對應(yīng)的路徑募判，初始dis就是對應(yīng)點之間的距離，初始path全部是-1咒唆。
2. 對于每一對頂點 u 和 v届垫，看看是否存在一個頂點 w 使得從 u 到 w 再到 v 比己知的路徑更短。如果是就更新它钧排。(自己到自己的頂點對肯定不用判斷)
   狀態(tài)轉(zhuǎn)移方程</br> 如果dis[u][v]>dis[u][w]+dis[w][v]成立</br>
   則：dis[u][v]=dis[u][w]+dis[w][v],,,,,path[u][v] = path[u][w]

看下面的圖敦腔，我們來分析下

tree28.jpg

1.初始化dis和path數(shù)組

2.圖中所有頂點對有(0,1)(1,0)(0,2)(2,0)(0,3)(3,0)(1,2)(2,1)(1,3)(3,1)(2,3)(3,2)對于以上每一個頂點對，對經(jīng)過點0(A)的松弛判斷恨溜，根據(jù)狀態(tài)轉(zhuǎn)移方程進行修改dis和path的值符衔。首先(0,1)頂點對中間點是0的松弛判斷找前，dis[0][1]=dis[0][0]+dis[0][1],所以狀態(tài)方程不成立。因為此圖是無向圖判族，所以(0,1)(1,0)頂點對判斷一個就行了躺盛。接著(0,2)中間點還是0,dis[0][2]=dis[0][0]+dis[0][2]還是不成立。接著(0,3)此時dis[0][3]=dis[0][0]+dis[0][3]還是不成立形帮，接著(1,2)發(fā)現(xiàn)dis[1][2]>dis[1][0]+dis[0][2];所以設(shè)置dis[1][2]=dis[1][0]+dis[0][2]=5,并更新path[1][2] =0;并同步更新(2,1)的dis數(shù)組和path數(shù)組槽惫。接著來到(1,3),dis[1][3]<dis[1][0]+dis[0][3]不更新。接著是(2,3)dis[2][3]>dis[2][0]+dis[0][3],所以修改dis[2][3]=dis[2][0]+dis[0][3]=0,并更新path[2][3]=0;辩撑，同步修改(3,2)的dis數(shù)組和path數(shù)組,如下表

3.接下來還是頂點對(0,1)(1,0)(0,2)(2,0)(0,3)(3,0)(1,2)(2,1)(1,3)(3,1)(2,3)(3,2),對于每一個頂點對經(jīng)過點1(B)的松弛判斷

4.經(jīng)過點2(C)的松弛判斷

5.經(jīng)過點3(D)的松弛判斷

此時dis數(shù)組和path數(shù)組全部更新完畢界斜，現(xiàn)在dis數(shù)組存儲的是兩個點之間的最短距離，path數(shù)組對應(yīng)的就是兩個點間的路徑過程合冀。這個path查看路徑是個遞歸的過程各薇。

核心代碼

//Floyd算法
void Floyd(struct MGraph *g)
{
    int i, j, k,temp=0;
    int **dis, **path;
    dis = (int**)malloc(sizeof(int*) * g->numVretexes);
    path = (int**)malloc(sizeof(int*) * g->numVretexes);
    for (i = 0; i < g->numVretexes; i++)
    {
        dis[i] = (int*)malloc(sizeof(int) *g->numVretexes);
        path[i] = (int*)malloc(sizeof(int) *g->numVretexes);
    }
    //初始化dis和path數(shù)組
    for (i = 0; i < g->numVretexes; i++)
    {
        for (j = 0; j < g->numVretexes; j++)
        {
            dis[i][j] = g->data[i][j];
            path[i][j] = -1;
        }
    }
    //開始逐個點p的判斷
    for (i = 0; i < g->numVretexes; i++)
    {
        //逐個取出每兩個點x,y，判斷dis[x][y] > dis[x][p]+dis[p][y]
        for (j = 0; j < g->numVretexes; j++)
        {
            for (k = 0; k < g->numVretexes; k++)
            {
                if (dis[j][k] > dis[j][i] + dis[i][k])
                {
                    dis[j][k] = dis[j][i] + dis[i][k];
                    path[j][k] = i;
                }
            }
        }
    }

    //輸出最短距離
    for (i = 0; i < g->numVretexes; i++)
    {
        for (j = 0; j < g->numVretexes; j++)
        {
            if (i != j)
            {
                //printf_s("%c-->%c(%d)", g->vetex[i], g->vetex[j], dis[i][j]);
                print_Path(i, j, g, path);
                printf("%d\n", dis[i][j]);
            }
        }
    }
}

獲取完整代碼

我分別用C君躺，C++峭判，JAVA三種主流語言編寫了完整代碼，請大家指導批正棕叫，一起學習林螃。

點擊查看