【算法學(xué)習(xí)】最短路徑問(wèn)題

最短路徑問(wèn)題

大家好，這里是新來(lái)的工人~

是一個(gè)沒(méi)學(xué)過(guò)太多算法編程內(nèi)容的rookie

所以文章的問(wèn)題也不難，歡迎小白們一起來(lái)看

語(yǔ)言用的是C++，當(dāng)然，算法部分比較重要

希望第一篇文章能寫(xiě)好，

讓同為小白的讀者讀懂吧~

話不多說(shuō)，那就開(kāi)始本期的內(nèi)容吧

目錄

01 問(wèn)題介紹

02 深度優(yōu)先遍歷

03 Floyd算法

04?Dijkstra算法

05 Bellman-Ford算法

06?SPFA算法

07?算法總結(jié)

01

問(wèn)題介紹

?

簡(jiǎn)單地說(shuō)，就是給定一組點(diǎn)，給定每個(gè)點(diǎn)間的距離，求出點(diǎn)之間的最短路徑。舉個(gè)例子，乘坐地鐵時(shí)往往有很多線路，連接著不同的城市。每個(gè)城市間距離不一樣，我們要試圖找到這些城市間的最短路線。

路徑問(wèn)題大概有以下幾種：

• 確定起點(diǎn)的最短路徑問(wèn)題：已知起始點(diǎn)，求起點(diǎn)到其他任意點(diǎn)最短路徑的問(wèn)題。即單源最短路徑問(wèn)題。

• 確定終點(diǎn)的最短路徑問(wèn)題：與確定起點(diǎn)的問(wèn)題相反，該問(wèn)題是已知終點(diǎn)，求最短路徑的問(wèn)題。在無(wú)向圖（即點(diǎn)之間的路徑?jīng)]有方向的區(qū)別）中該問(wèn)題與確定起點(diǎn)的問(wèn)題完全等同，在有向圖（路徑間有確定的方向）中該問(wèn)題等同于把所有路徑方向反轉(zhuǎn)的確定起點(diǎn)的問(wèn)題。

• 確定起點(diǎn)終點(diǎn)的最短路徑問(wèn)題：已知起點(diǎn)和終點(diǎn)，求任意兩點(diǎn)之間的最短路徑。即多源最短路徑問(wèn)題。?

?

我們先說(shuō)明如何輸入一個(gè)圖，并以此為例：

我們通過(guò)這樣的形式輸入數(shù)據(jù)：
5 8?
1 2 2?
1 5 10?
2 3 3
2 5 7?
3 1 4?
3 4 4?
4 5 5?
5 3 3

其中，第一行表示共有5個(gè)點(diǎn)（可以理解為城市），8條邊（理解為路）。

注意，這里一行的三個(gè)數(shù)據(jù)分別表示i點(diǎn)，j點(diǎn)，和從i到j(luò)的單向距離！單向！單向！

?

我們直接輸出最短路程。（也可以加上標(biāo)記輸出路徑）?

在具體解決問(wèn)題之前，我們先要把這些數(shù)據(jù)存儲(chǔ)起來(lái)，方便調(diào)用。

這里我們直接用一個(gè)二維數(shù)組來(lái)模擬這個(gè)圖（它的名字叫鄰接矩陣）：

?

∞表示到達(dá)不了。

?

在圖中，第i列第j行表示的是i到j(luò)的距離。其中，將到自己的距離定義為0，用無(wú)窮定義沒(méi)有路徑連通。存儲(chǔ)到數(shù)組中，可以通過(guò)二維數(shù)組表示。

?

下面我們就開(kāi)始分別講解幾種解決最短路徑問(wèn)題的經(jīng)典算法。

?

02

深度優(yōu)先遍歷（DFS）

我們知道，深度優(yōu)先搜索常用于走迷宮，是一種遍歷全圖的暴力方法。同理，我們利用深度優(yōu)先遍歷，也是通過(guò)暴力遍歷全圖的方法來(lái)找到最短路徑。

?

因?yàn)槲覀兛梢栽谳斎霐?shù)據(jù)是對(duì)城市進(jìn)行編號(hào)，所以我們將問(wèn)題的描述改為求從1號(hào)城市到5號(hào)城市的最短路徑長(zhǎng)度?。（即初始城市到最后的城市）

?

我們通過(guò)DFS遞歸函數(shù)，從起始1號(hào)城市起，不斷地判斷是否可以通過(guò)一個(gè)城市到達(dá)最后的5號(hào)城市（在回溯中判斷），然后記錄最小路程，不斷更新。

?

關(guān)于深度優(yōu)先搜索的知識(shí)在此就不細(xì)講了，有興趣的朋友可以自行搜索。

這里直接附上C++的代碼，講解見(jiàn)注釋。

//DFS解最短路徑問(wèn)題 
#include using namespace std;const int INF=99999999;//正無(wú)窮int minn=INF;int n,dist[105][105],book[105];void dfs(int cur,int dis){    int j;    //一點(diǎn)點(diǎn)優(yōu)化：如果本次查找的路徑到此已經(jīng)超過(guò)前面查找的最短路徑總長(zhǎng)，就不需要再繼續(xù)了    if(dis>minn)        return;    if(cur==n)//到達(dá)要查的城市     {        minn=min(dis,minn);        return;    }    for(j=1;j<=n;j++)//從1號(hào)城市到n號(hào)城市依次嘗試看是否能通過(guò)j到達(dá)n     {        if(dist[cur][j]!=INF&&book[j]==0)//判斷當(dāng)前城市cur到城市j是否有路，并判斷城市j是否已經(jīng)走過(guò)        {            book[j]=1;//標(biāo)記已經(jīng)走過(guò)            dfs(j,dis+dist[cur][j]);//從城市j再出發(fā)，繼續(xù)尋找            book[j]=0;        }    }    return;}int main(){    int i,j,m,a,b,c;    cin>>n>>m;    //初始化二維矩陣    for(i=1;i<=n;i++)        for(j=1;j<=n;j++)            if(i==j)    dist[i][j]=0;   //到自己的距離為0                else    dist[i][j]=INF;  //距離為無(wú)限，默認(rèn)到不了             //讀入城市之間的距離            for(i=1;i<=m;i++)            {                cin>>a>>b>>c;                dist[a][b]=c;            }            //從1號(hào)城市出發(fā),接下來(lái)就交給函數(shù)dfs了~             book[1]=1;            dfs(1,0);            cout<        return 0;}

?

可能有人會(huì)問(wèn)，深度優(yōu)先搜索的兄弟廣度優(yōu)先搜索算法呢？事實(shí)上，基于廣度優(yōu)先遍歷依照節(jié)點(diǎn)到初始點(diǎn)的節(jié)點(diǎn)數(shù)遍歷全圖的特點(diǎn)，它能解決沒(méi)有權(quán)值（也就是默認(rèn)每條路程一樣長(zhǎng)）的圖的最小路徑問(wèn)題，但對(duì)有權(quán)值的圖，BFS很難解決（即使加上minn指標(biāo)，我們也無(wú)法處理“回頭”的路徑）。我們就不在此講解了。

貼上運(yùn)行結(jié)果：

03

Floyd算法

?

Floyd它可以方便地求出任意兩點(diǎn)間的距離，求的是多源最短路徑。最大的優(yōu)點(diǎn)就是容易理解和編寫(xiě)，算法的核心代碼只有5行：

     //核心代碼     for(k=1;k<=n;k++)         for(i=1;i<=n;i++)             for(j=1;j<=n;j++)                if(dist[i][k]+dist[k][j]?????????????????????dist[i][j]=dist[i][k]+dist[k][j];?

但看了代碼后童鞋們會(huì)發(fā)現(xiàn)，F(xiàn)loyd算法的時(shí)間復(fù)雜度比較高(n^3)，不適合計(jì)算大量數(shù)據(jù)。

?

我們可以把Floyd算法理解為“如果兩點(diǎn)間的路徑長(zhǎng)度，大于這兩點(diǎn)通通過(guò)第三點(diǎn)連接的路徑長(zhǎng)度，那么就修正這兩點(diǎn)的最短路徑”。

?

下面我們來(lái)具體講解一下算法的思路：

在代碼中，i，j表示的是我們當(dāng)前循環(huán)中所求的起點(diǎn)、終點(diǎn)。k則是我們引入的“中轉(zhuǎn)點(diǎn)”。為什么要引入中轉(zhuǎn)點(diǎn)呢？因?yàn)楫?dāng)我們尋找i、j之間的最短路徑時(shí)，要么是i、j間的距離，要么就是經(jīng)過(guò)其他點(diǎn)中轉(zhuǎn)：i→k→。。。→j。

?

為了方便講解，我們給出一個(gè)概念“松弛”：如果dist【i】【j】>dist【i】【k】+dist【k】【j】（e表示兩點(diǎn)間的距離），我們把dist【i】【j】更新為dist【i】【k】+dist【k】【j】，達(dá)到“經(jīng)過(guò)中轉(zhuǎn)點(diǎn)k后距離縮短，并記錄”的目的。

?

在第1輪循環(huán)中，我們以1為中轉(zhuǎn)點(diǎn)，把任意兩條邊的距離松弛一遍，更新數(shù)組數(shù)據(jù)。

在第2輪循環(huán)中，我們以2為中轉(zhuǎn)點(diǎn)，再松弛一遍。這時(shí)，對(duì)第1輪松弛更新過(guò)的數(shù)據(jù)，如果繼續(xù)更新，相當(dāng)于中轉(zhuǎn)到1，2后取得當(dāng)前最短路徑。

。。。。。。

最后得到的數(shù)組就是任意兩點(diǎn)間的最短路徑。

?

這個(gè)時(shí)候再看一遍這句話：“如果兩點(diǎn)間的路徑長(zhǎng)度，大于這兩點(diǎn)通通過(guò)第三點(diǎn)連接的路長(zhǎng)度，那么就修正這兩點(diǎn)的最短路徑?！笔遣皇蔷湍軌蚶斫饬耍?/span>

?

下面放碼。

?

//Floyd算法解最短路徑問(wèn)題 #include using namespace std;
const int INF=99999;
int main(){  //讀入數(shù)據(jù)的過(guò)程和dfs沒(méi)什么區(qū)別，就不講解了     int i,j,n,m,k,a,b,c;    int dist[105][105];    cin>>n>>m;    for(i=1;i<=n;i++)        for(j=1;j<=n;j++)            if(i==j)    dist[i][j]=0;                  else    dist[i][j]=INF;              for(i=1;i<=m;i++)            {                cin>>a>>b>>c;                dist[a][b]=c;            }
     //核心代碼     for(k=1;k<=n;k++)         for(i=1;i<=n;i++)             for(j=1;j<=n;j++)                if(dist[i][k]+dist[k][j]                     dist[i][j]=dist[i][k]+dist[k][j];      for (i=1;i<=n;i++){       for(j=1;j<=n;j++){         cout<"\t";     }     cout<<endl;   }
        return 0;}

?

04

Dijkstra算法

Dijkstra?算法主要解決的是單源最短路徑問(wèn)題。它的時(shí)間復(fù)雜度一般是o(n^2) ，因此相對(duì)于Floyd算法速度上有極大的優(yōu)勢(shì)，可以處理更多的數(shù)據(jù)。

?

算法的核心依舊是上文講到的“松弛”。只不過(guò)松弛的方式略有不同：它通過(guò)不斷選擇距離起點(diǎn)最近的頂點(diǎn)作為新的起點(diǎn)，再利用這些新的起點(diǎn)來(lái)松弛其他較遠(yuǎn)的點(diǎn)，最終計(jì)算出所有點(diǎn)到起點(diǎn)最短路徑。

這樣聽(tīng)起來(lái)有點(diǎn)繞，我們基于代碼，通過(guò)例子來(lái)講解。

?

我們把點(diǎn)i到起點(diǎn)1的距離定義為dis【i】（現(xiàn)在知道我上面為什么用dist了吧！），用一個(gè)book來(lái)標(biāo)記該點(diǎn)是否已經(jīng)為最短狀況，初始化為0（否）

?

核心代碼分為兩部分：第一部分判斷最小，第二部分進(jìn)行松弛。

以原題為例：

第一次循環(huán)，我們先進(jìn)入第一部分判斷較短距離。第一次到起點(diǎn)1只有2號(hào)，5號(hào)點(diǎn)有最短距離，分別為2，10。

下一步，我們找到2，5號(hào)中到起點(diǎn)1距離較短的點(diǎn)u（這里是2號(hào)）。

進(jìn)入第二部分松弛。對(duì)點(diǎn)v，如果v到起點(diǎn)1的距離大于u（即2）到1的距離加上2到v的距離，更新v到原點(diǎn)的距離dis【v】。

開(kāi)始循環(huán)。

在下一次循環(huán)中，相當(dāng)于把點(diǎn)2當(dāng)作新的起點(diǎn)代替點(diǎn)1，進(jìn)行上述操作。

?

可以看出，Dijkstra是一種基于貪心策略的算法，也是一種以DFS為思路的算法。

#貪心算法是指，在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體最優(yōu)上加以考慮，貪心算法所做出的是在某種意義上的局部最優(yōu)解。#

?

為什么下一條次較短路徑要這樣選擇？（貪心準(zhǔn)則的正確性）

因?yàn)槲覀兯愕氖堑狡瘘c(diǎn)的距離，所以所有路徑必然要經(jīng)過(guò)與起點(diǎn)最近的2（或不經(jīng)過(guò)任何別的中轉(zhuǎn)點(diǎn)），而相對(duì)于2點(diǎn)，5號(hào)點(diǎn)距離更遠(yuǎn)，還有通過(guò)2點(diǎn)松弛之后縮短路徑的可能性，所以我們直接選擇2為新的起點(diǎn)進(jìn)行下一步松弛。那么，第k次循環(huán)就表示松弛了k次，即經(jīng)過(guò)?了k-1個(gè)中轉(zhuǎn)點(diǎn)（或k-1條邊）才到達(dá)起點(diǎn)1，留在dis（）數(shù)組中的距離就是經(jīng)過(guò)中轉(zhuǎn)點(diǎn)個(gè)數(shù)<=k-1（可能無(wú)需經(jīng)過(guò)這么多個(gè)點(diǎn)就達(dá)到）的最短路徑。

?

Dijkstra算法主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑算法，直到擴(kuò)展到最遠(yuǎn)點(diǎn)（指經(jīng)過(guò)的中轉(zhuǎn)點(diǎn)最多，）為止。（這里就是類(lèi)似BFS的地方）

?

選擇最短路徑頂點(diǎn)的時(shí)候依照的是實(shí)現(xiàn)定義好的貪心準(zhǔn)則，所以該算法也是貪心算法的一種。

還有說(shuō)法是Dijkstra也屬于動(dòng)態(tài)規(guī)劃。這里我就不發(fā)表言論了，因?yàn)楸拘“走€不懂(┬＿┬)。

下面給出代碼。

//Dijkstra算法解最短路徑問(wèn)題 #includeusing namespace std;
const int INF=99999;
int main(){     int dist[105][105] ;   int dis[105]  ;   int book[105] ;   int i,j,n,m,a,b,c,u,v,Min;
     cin>>n>>m;
     //開(kāi)始了！??！     for(i = 1;i <= n;i++)  //每輪循環(huán)計(jì)算的是中轉(zhuǎn)點(diǎn)為n-1時(shí)的最小點(diǎn)。          for(j = 1;j <= n;j++)              if(i == j)  dist[i][j] = 0;              else        dist[i][j] = INF;
              for(i = 1;i <= m;i++)              {                    cin>>a>>b>>c;                    dist[a][b] = c;              }          for(i = 1;i <= n;i++)                            dis[i] = dist[1][i];
          for(i = 1;i<=n;i++)   //初始化標(biāo)記book                    book[i] = 0;                   book[1] = 1;
          for(i = 1;i <= n-1;i++)  //篩出當(dāng)前沒(méi)有訪問(wèn)的并且與上一點(diǎn)直接相連的距離最小的點(diǎn)。        {               Min = INF;               for(j = 1;j <= n;j++)               {                     if(book[j] == 0&& dis[j] < Min)                     {                           Min = dis[j];                           u = j;                     }               }

          book[u] = 1;          for(v = 1;v <= n;v++) //松弛          {                if(dist[u][v] < INF)                {                      if(dis[v] > dis[u] + dist[u][v])                           dis[v] = dis[u] + dist[u][v];                }          }        }        for(i  = 1;i <= n;i++)            cout<"\t";
    return 0;}

?

05

Bellman－Ford算法

?

與Floyd算法一樣，Dijkstra也有自己的問(wèn)題，那就是無(wú)法處理“路徑長(zhǎng)度”為負(fù)的情況。（當(dāng)然，城市間的距離不可能為負(fù)，但在一些特殊的問(wèn)題中，路徑的長(zhǎng)度也可以為負(fù)）

?

為什么呢？以第一次循環(huán)為例，我們?cè)诘谝淮闻袛噙x擇了點(diǎn)2為“新起點(diǎn)”，而沒(méi)有考慮別的點(diǎn)經(jīng)過(guò)點(diǎn)5達(dá)到起點(diǎn)1松弛的可能性。假設(shè)，點(diǎn)3到點(diǎn)2的距離為1，點(diǎn)3到點(diǎn)5的距離為-100，那點(diǎn)3經(jīng)過(guò)點(diǎn)5松弛的路徑實(shí)際上更短，而在Dijkstra中，卻被我們忽視了。

?

所以，我們介紹Bellman－Ford算法來(lái)解決這種問(wèn)題。（而且代碼的編寫(xiě)也很簡(jiǎn)單，我很喜歡~~）

     //Bellman－Ford算法核心部分      for(k = 1;k <= n;k++)         for(i = 1;i <= m;i++)            if(dis[v[i]]>dis[u[i]]+w[i])                dis[v[i]] = dis[u[i]]  + w[i];     for(i = 1;i <= m;i++)            if(dis[v[i]]>dis[u[i]]+w[i])

?

我們來(lái)講解一下。

可以從代碼中看到Bellman-ford與Dijkstra有相似的地方，都是通過(guò)松弛操作來(lái)達(dá)到最短路徑。不同的是，Dijkstra是通過(guò)從近到遠(yuǎn)的順序來(lái)按點(diǎn)的順序松弛，Bellman-ford則是按輸入時(shí)對(duì)每一條邊的順序來(lái)松弛。

?

代碼中的數(shù)組u（），v（），w（）分別存儲(chǔ)一行輸入的三個(gè)數(shù)據(jù)（i點(diǎn)，j點(diǎn)，i到j的單向距離），這意味著在前文提到的鄰接矩陣被我們棄用了，dist（）數(shù)組不會(huì)在這里出現(xiàn)了。

?

最外輪的k循環(huán)表示每次通過(guò)k個(gè)中轉(zhuǎn)點(diǎn)（這里與Dijkstra相同，同樣我們可以理解為經(jīng)過(guò)的邊的條數(shù)），i循環(huán)表示枚舉m條邊。

?

看過(guò)前面對(duì)Dijkstra的講解，這里應(yīng)該不難理解了：對(duì)每一條編號(hào)為i的邊，我們比較邊i的起點(diǎn)v[i]到起點(diǎn)1的距離dis[v[i]]與邊i的另一點(diǎn)u[i]到起點(diǎn)1的距離+ v[i]，u[i]的間距dis[u[i]]? + w[i]，更新dis（j）。（好繞。。。）那么，第k次循環(huán)就表示松弛了k次，即經(jīng)過(guò)?了k-1個(gè)中轉(zhuǎn)點(diǎn)（或k-1條邊）才到達(dá)起點(diǎn)1，留在dis（）數(shù)組中的距離就是經(jīng)過(guò)中轉(zhuǎn)點(diǎn)個(gè)數(shù)<=k-1（可能無(wú)需經(jīng)過(guò)這么多個(gè)點(diǎn)就達(dá)到）的最短路徑。（細(xì)心的朋友可以發(fā)現(xiàn)這句話在前文中出現(xiàn)過(guò)）

?

下面回到負(fù)值路徑的問(wèn)題上。因?yàn)槲覀兪峭ㄟ^(guò)邊為順序松弛的，在這個(gè)過(guò)程中沒(méi)有放棄對(duì)任何一條邊（在Dijkstra中，我們放棄了部分?jǐn)?shù)據(jù)，比如點(diǎn)5到點(diǎn)3的路徑），所以不會(huì)有忽視的情況，自然也就能處理負(fù)值邊了~

?

我們甚至還能判斷負(fù)權(quán)回路（指一個(gè)回路的路徑總和為負(fù)）。

?

等等，我們是不是還沒(méi)提過(guò)為什么松弛n-1次后一定能得到最短路徑？

1. 1.??????????當(dāng)沒(méi)有負(fù)權(quán)回路時(shí)，對(duì)于超過(guò)n-1條邊而到達(dá)起點(diǎn)1的路徑，一定存在正值回路，肯定可以去掉；

2. 2.?????????當(dāng)有負(fù)權(quán)回路時(shí)，我們可以無(wú)限次地在回路里循環(huán)，讓路徑無(wú)限小，也就沒(méi)有“最短路徑了”。

?

因此，n-1次的松弛必然得到最短路徑。

?

我們就基于2來(lái)判斷負(fù)權(quán)回路。在循環(huán)n-1次后再對(duì)每一條邊松弛一次，如果有還能繼續(xù)松弛的邊，則存在負(fù)權(quán)回路。（）

?

我們來(lái)看看完整版代碼：

//Bellman－Ford算法解最短路徑問(wèn)題 #includeusing namespace std;
const int INF=99999;
int main(){     int dis[105] , i , k , n , m , u[105] , v[105] , w[105];     bool flag=false;     cin>>n>>m;
     for(i  = 1;i <= m;i++)           cin>>u[i]>>v[i]>>w[i];
     for(i = 1;i <= n;i++)          dis[i] = INF;     dis[1] = 0;
     //Bellman－Ford算法核心部分      for(k = 1;k <= n;k++)         for(i = 1;i <= m;i++)            if(dis[v[i]]>dis[u[i]]+w[i])                dis[v[i]] = dis[u[i]]  + w[i];     for(i = 1;i <= m;i++)            if(dis[v[i]]>dis[u[i]]+w[i])                  flag=true;
      if (!flag)         for(i = 1;i <= n;i++)               cout<"\t";      else            cout<<"存在負(fù)權(quán)回路??！";
}

06

SPFA算法

?

呼，終于來(lái)到最后一個(gè)了。。。

之前我們?cè)谡劦?/span>Bellman-ford能處理負(fù)值路徑是提到，Bellman-ford沒(méi)有放棄對(duì)任何一條邊的松弛。這雖然不錯(cuò)，但也會(huì)是我們優(yōu)化的一個(gè)方向。（具體的說(shuō)，大神們優(yōu)化的方向）

?

我們可以加入一個(gè)判斷，判斷某一條邊是否被別的點(diǎn)幫助松弛過(guò)，因?yàn)?strong>只有被松弛過(guò)的點(diǎn)才能松弛別的點(diǎn)（被起點(diǎn)松弛也是松弛）。當(dāng)一個(gè)點(diǎn)無(wú)法被松弛時(shí)，在本次經(jīng)過(guò)k-1條邊，它還無(wú)法接觸到起點(diǎn)1（或者在更早的時(shí)候就已經(jīng)被判斷過(guò)了），也就沒(méi)有幫助他人的能力。這是一個(gè)遞推的過(guò)程，需要想明白。如果存在有一個(gè)點(diǎn)壓根就沒(méi)能力支援，也就是它本身已經(jīng)沒(méi)有存在的價(jià)值了，那么我們下次就不用再考慮它了。

?

注意，在這里我們依然我們始終保留了對(duì)負(fù)權(quán)路徑、回路的判斷。

?

我們可以利用隊(duì)列來(lái)存放可以繼續(xù)幫助松弛的點(diǎn)，舍棄沒(méi)有利用價(jià)值的點(diǎn)。這和BFS是一個(gè)道理，一邊要保證有k-1輪大循環(huán)來(lái)控制，一方面又要舍棄舊點(diǎn)增加新點(diǎn)，隊(duì)列就可以有這個(gè)作用。所以當(dāng)代碼寫(xiě)出來(lái)是你會(huì)驚訝地發(fā)現(xiàn)，它和BFS的形式是那么地相似。

?

也不知道講明白沒(méi)，就先放代碼吧。

//SPFA解最短路徑問(wèn)題 #include using namespace std;
int main(){  int n,m,i,j,k;  int dis[105]={0},book[105]={0};  //book數(shù)組用來(lái)記錄哪些頂點(diǎn)已經(jīng)在隊(duì)列中   int que[1000]={0},head=1,tail=1;//定義一個(gè)隊(duì)列，并初始化隊(duì)列  int dist[105][105];  int INF = 99999999;  int a,b,c;  cin>>n>>m;  //初始化   for(i=1;i<=n;i++)    dis[i]=INF;  dis[1]=0;   for(i=1;i<=n;i++)    book[i] = 0; //初始化為0，剛開(kāi)始都不在隊(duì)列中    //初始化二維矩陣    for(i=1;i<=n;i++)        for(j=1;j<=n;j++)            if(i==j)    dist[i][j]=0;   //到自己的距離為0                else    dist[i][j]=INF;  //距離為無(wú)限，默認(rèn)到不了             //讀入城市之間的距離            for(i=1;i<=m;i++)            {                cin>>a>>b>>c;                dist[a][b]=c;            }  //1號(hào)頂點(diǎn)入隊(duì)  que[tail]=1; tail++;  book[1]=1;//標(biāo)記1號(hào)頂點(diǎn)已經(jīng)入隊(duì)  while(head//隊(duì)列不為空的時(shí)候循環(huán)      for (i=1;i<=n;i++)        if (dist[que[head]][i]!=INF && i!=que[head])        {          k=i;  // k表示每一條邊的對(duì)應(yīng)頂點(diǎn)           if(dis[k]>dist[que[head]][k]+dis[que[head]] ) //判斷是否松弛成功         {                 dis[k]=dist[que[head]][k]+dis[que[head]];              //這的book數(shù)組用來(lái)判斷頂點(diǎn)v[k]是否在隊(duì)列中                /*如果不使用一個(gè)數(shù)組來(lái)標(biāo)記的話，判斷一個(gè)頂點(diǎn)是否在隊(duì)列中每次                都 需要從隊(duì)列的head到tail掃一遍，很浪費(fèi)時(shí)間*/              if(book[k]==0)//0表示不在隊(duì)列中，將頂點(diǎn)v[k]加入隊(duì)列中                //下面兩句為入隊(duì)操作            {              que[tail] = k;              tail++;              //同時(shí)標(biāo)記頂點(diǎn)v[k]已經(jīng)入隊(duì)             book[k] =1;                }        }       }    //出隊(duì)    book[que[head]] = 0;    head++;   }  for(i=1;i<=n;i++)    cout<"\t";  return 0; }

?

?

#網(wǎng)上很多資料提到SPFA都會(huì)提到鄰接表，這里我為了偷懶就隨便講下啦~~代碼中我用的是鄰接矩陣存儲(chǔ)的，請(qǐng)放心食用。

大致是因?yàn)椋?dāng)圖的邊數(shù)較少時(shí)（相對(duì)于頂點(diǎn)而言，邊數(shù)M<頂點(diǎn)數(shù)N^2）（我們稱為稀疏圖，對(duì)應(yīng)稠密圖），用這樣的方法來(lái)存儲(chǔ)可以極大地降低時(shí)間復(fù)雜度。

大致是利用了鏈表的原理實(shí)現(xiàn)的。有興趣可以自己搜索。#

07

算法總結(jié)

? ? ?這里直接盜用一張網(wǎng)絡(luò)上的表來(lái)總結(jié)：

?

?

是不是感覺(jué)清晰些了？

那么，本期的內(nèi)容到這里就全部結(jié)束了。

這里是新來(lái)的工人小舟，

正走在努力學(xué)習(xí)編程的路上。

讓我們下次再見(jiàn)！

#

-The End-

文/怎么學(xué)都學(xué)不會(huì)C++的新手舟

版/怎么趕都趕不完作業(yè)的小白舟

碼/新來(lái)到程序猿聲的工人舟

審/這片工地的包工頭短短的路走走停停

#