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

最短路徑問題

大家好，這里是新來的工人~

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

所以文章的問題也不難，歡迎小白們一起來看

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

希望第一篇文章能寫好，

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

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

目錄

01 問題介紹

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

03 Floyd算法

04?Dijkstra算法

05 Bellman-Ford算法

06?SPFA算法

07?算法總結(jié)

01

問題介紹

?

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

路徑問題大概有以下幾種：

• 確定起點的最短路徑問題：已知起始點，求起點到其他任意點最短路徑的問題。即單源最短路徑問題。

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

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

?

我們先說明如何輸入一個圖，并以此為例：

我們通過這樣的形式輸入數(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個點（可以理解為城市），8條邊（理解為路）。

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

?

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

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

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

?

∞表示到達不了。

?

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

?

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

?

02

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

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

?

因為我們可以在輸入數(shù)據(jù)是對城市進行編號，所以我們將問題的描述改為求從1號城市到5號城市的最短路徑長度?。（即初始城市到最后的城市）

?

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

?

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

這里直接附上C++的代碼，講解見注釋。

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

?

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

貼上運行結(jié)果：

03

Floyd算法

?

Floyd它可以方便地求出任意兩點間的距離，求的是多源最短路徑。最大的優(yōu)點就是容易理解和編寫，算法的核心代碼只有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];?

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

?

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

?

下面我們來具體講解一下算法的思路：

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

?

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

?

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

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

。。。。。。

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

?

這個時候再看一遍這句話：“如果兩點間的路徑長度，大于這兩點通通過第三點連接的路長度，那么就修正這兩點的最短路徑。”是不是就能夠理解了？

?

下面放碼。

?

//Floyd算法解最短路徑問題 #include using namespace std;
const int INF=99999;
int main(){  //讀入數(shù)據(jù)的過程和dfs沒什么區(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?算法主要解決的是單源最短路徑問題。它的時間復(fù)雜度一般是o(n^2) ，因此相對于Floyd算法速度上有極大的優(yōu)勢，可以處理更多的數(shù)據(jù)。

?

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

這樣聽起來有點繞，我們基于代碼，通過例子來講解。

?

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

?

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

以原題為例：

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

下一步，我們找到2，5號中到起點1距離較短的點u（這里是2號）。

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

開始循環(huán)。

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

?

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

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

?

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

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

?

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

?

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

還有說法是Dijkstra也屬于動態(tài)規(guī)劃。這里我就不發(fā)表言論了，因為本小白還不懂(┬＿┬)。

下面給出代碼。

//Dijkstra算法解最短路徑問題 #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;
     //開始了！！！     for(i = 1;i <= n;i++)  //每輪循環(huán)計算的是中轉(zhuǎn)點為n-1時的最小點。          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)前沒有訪問的并且與上一點直接相連的距離最小的點。        {               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也有自己的問題，那就是無法處理“路徑長度”為負(fù)的情況。（當(dāng)然，城市間的距離不可能為負(fù)，但在一些特殊的問題中，路徑的長度也可以為負(fù)）

?

為什么呢？以第一次循環(huán)為例，我們在第一次判斷選擇了點2為“新起點”，而沒有考慮別的點經(jīng)過點5達到起點1松弛的可能性。假設(shè)，點3到點2的距離為1，點3到點5的距離為-100，那點3經(jīng)過點5松弛的路徑實際上更短，而在Dijkstra中，卻被我們忽視了。

?

所以，我們介紹Bellman－Ford算法來解決這種問題。（而且代碼的編寫也很簡單，我很喜歡~~）

     //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])

?

我們來講解一下。

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

?

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

?

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

?

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

?

下面回到負(fù)值路徑的問題上。因為我們是通過邊為順序松弛的，在這個過程中沒有放棄對任何一條邊（在Dijkstra中，我們放棄了部分?jǐn)?shù)據(jù)，比如點5到點3的路徑），所以不會有忽視的情況，自然也就能處理負(fù)值邊了~

?

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

?

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

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

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

?

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

?

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

?

我們來看看完整版代碼：

//Bellman－Ford算法解最短路徑問題 #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算法

?

呼，終于來到最后一個了。。。

之前我們在談到Bellman-ford能處理負(fù)值路徑是提到，Bellman-ford沒有放棄對任何一條邊的松弛。這雖然不錯，但也會是我們優(yōu)化的一個方向。（具體的說，大神們優(yōu)化的方向）

?

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

?

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

?

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

?

也不知道講明白沒，就先放代碼吧。

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

?

?

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

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

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

07

算法總結(jié)

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

?

?

是不是感覺清晰些了？

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

這里是新來的工人小舟，

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

讓我們下次再見！

#

-The End-

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

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

碼/新來到程序猿聲的工人舟

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

#