圖的基礎，最短路徑的幾種解答

單源最短路： Bellman-Ford & Dijkstra 及其簡單優化以及負圈的判斷

多源最短路：Floyd-Warshall 算法的簡單了解

路徑還原問題

CSDN Markdown似乎C++代碼有問題可轉我的個人部落格網站

https://joke-lin.github.io/2018/12/07/ShortestPath/

最短路徑的三種算法以及路徑還原與負圈判斷

算法代碼及思路主要參考：《挑戰程式設計競賽》

在此之前讀者應對圖已經有基礎的概念，以及圖的鄰接表 & 鄰接矩陣的表示方法

Bellman-Ford

單源最短路問題是固定一個起點，然後求這個點到其他各個頂點的最短路（最小權值和）

設起點s到其他頂點i的距離為 d[i] 則很容易可以得到下面這個結論：

d [ i ] = m i n { d [ j ] + e d g e ( j , i ) } e d g e ( j , i ) ∈ E d[i] = min\{d[j] + edge(j,i)\} edge(j,i) \in E d[i]=min{d[j]+edge(j,i)}edge(j,i)∈E

設定初始狀态d[s] = 0 else d[i] = INF 然後隻要在循環裡不斷更新這些值

如果不再更新說明所有路都已達到最短代碼如下：

struct Edge{ int from, to, cost;}; // 定義從點from指向to權值為cost的邊
Edge edges[MAXN];

int d[MAXN]; // 最短距離
int V,E; // V: 頂點數 E: 邊數

// 從點s到其他點的最小距離
void Bellman_Ford(int s)
{
    for(int i = 0;i < V;i++) d[i] = INF;
    d[s] = 0; // 到自己為0
    while(true)
    {
        bool isUpdate = false;
        for(int i = 0; i < E; i++)
        {
            Edge temp = edges[i];
            if(d[temp.from] != INF && d[temp.to] > d[temp.from]+temp.cost)
            {
                d[temp.to] = d[temp.from] + temp.cost;
                isUpdate = true;
            }
        }
        if(!isUpdate) break;
    }
}

如果圖中不存在s可達的負圈，那麼最短路不會經過一個頂點兩次，也就是說最多通過V-1條邊，也可以這樣理

解，每一次更新都會有更短的路徑産生，那麼在V個點的圖中，兩個點的最遠距離隻能是V-1條邊，是以循環最多

隻會執行V-1次，這個特性将是我們判斷是否存在負圈的重要性質

是以我們也可以将上面的代碼簡單化為：

void Bellman_Ford(int s) // 不存在負圈的情況
{
    for(int i = 0;i < V;i++) d[i] = INF;
    d[s] = 0; // 到自己為0
	for(int j = 0;j < V-1;j++)
    {
        for(int i = 0; i < E; i++)
        {
            Edge temp = edges[i];
            d[temp.to] = min(d[temp.to],d[temp.from]+temp.cost)
        }
    }
}

很容易可以看出來Bellman算法的複雜度為 O(V*E)

負圈的判斷

在這裡，首先要明确負圈（負權環）和負權邊的差別

負圈是指一條環狀路徑上的綜合權值為負的，負權邊是指權值為負數的邊，在算法中如果圖是無向圖的話，

負權邊和負圈是等價的。如下圖：也就是在A與B之間形成了一個環，這個環的權值為-2

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-ioe5g7Wx-1582460376581)(https://raw.githubusercontent.com/Joke-Lin/Joke-Lin.github.io/master/assets/ArticleImg/shortpath/shortpath1.png)]

是以在無向圖中負邊的存在也就是負圈的存在。是以Bellman主要是可以用來判斷有向圖中是否存在負圈。

隻要存在了負圈，那麼Bellman的松弛操作（也就是那個每次更新的内容）将會永遠的執行下去。

相當于沒走一個這個負圈總的權值（路徑長度）就會減少。但是我們上面已經得到在不存在負圈的圖中最多執行

V-1次循環，是以我們隻要判斷在第V次仍然更新了，那麼就存在負圈了。代碼隻要更改一點點就行：

void Bellman_Ford(int s) // 不存在負圈的情況
{
    for(int i = 0;i < V;i++) d[i] = INF;
    d[s] = 0; // 到自己為0
	for(int j = 0;j < V;j++)
    {
        for(int i = 0; i < E; i++)
        {
            Edge temp = edges[i];
            if(d[temp.from] != INF && d[temp.to] > d[temp.from]+temp.cost)
            {
                d[temp.to] = d[temp.from] + temp.cost;
                // 隻要再次加上到第V-1次的特判
                if(j == V-1)
                {
                    cout << "存在負圈" << endl;
                    return;
                }
            }
        }
    }
}

Dijkstra

我們先考慮不存在負邊的情況，在Bellman算法中每一次都要全部周遊所有的邊，而且如果d[i]本身不是最短路徑

那麼進行那個松弛操作之後的d[i]依然不是最短，是以可以對此進行優化：

找到最短路徑已經确定的頂點，更新從他出發相鄰頂點的最短距離
從此不需要在更新上面已經确定的哪些頂點（即不需要周遊）

這就衍生出了Dijkstra算法。上面兩點用圖來描述就是：

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-FzHjRKUt-1582460376584)(https://raw.githubusercontent.com/Joke-Lin/Joke-Lin.github.io/master/assets/ArticleImg/shortpath/shortpath2.png)]

假設初始點為A首先AC < AB

很清楚的我們可以得出結論AC就是A到C的最短路徑，因為如果從AB方向走的話，AB ＞AC 而且我們的圖是

沒有負邊的，是以BD > 0 也就是說AB + BD… > AC 是必然成立的。是以A->C的最短路徑已經确定了，之後就

需要再去管C點了。算法總的描述如下：

在最開始時，隻有起點的最短距離是确定的（而且所有點都未曾使用）。而在尚未使用的頂點中，距離d[i]最小的頂點就是最短距離已經确定的頂點。因為不存在負邊，是以d[i]不會在以後的更新中變小。這就是Dijkstra算法

代碼如下：

int cost[MAXN][MAXN]; // cost[i][j] 表示從i到j之間的權值（不存在是為INF）
int d[MAXN]; // 從起點到其他點的最短距離
bool used[MAXN]; // 已經使用過的圖（已經确定最短距離的點）
int V; // 點的個數

void Dijkstra(int s)
{
    fill(d,d+V,INF); // algorithm中的函數 将d數組全部賦為INF
    fill(used,used+V,false);
    d[s] = 0;
    
    while(true)    
    {
        int v = -1;
        // c從未使用過的點集中取一個距離最小的點
        for(int u = 0;u < V;u++)
        	if(!used[u] && (v == -1 || d[u] < d[v])) v = u;
        if(v == -1) break; // 所有的點的最短路徑确定則退出
       	used[v] = true;
        for(int u = 0;u < V;u++)
        {
            d[u] = min(d[u],d[v]+cost[v][u]);
        }
    }
}

簡單的優化

上面代碼的時間複雜度是 O(V2) , 我們可以通過堆（優先隊列）降為O(E*log(V))

上面有一個操作是找到距離最小的點和标記是否使用，這個就可以使用堆來優化

代碼如下：

typedef pair<int,int> P; // first 是最短距離 second 是頂點編号
struct edge{int to, cost};
vector<edge> G[MAXN]; // 使用鄰接表存圖
int d[MAXN]; // 從起點到其他點的最短距離
bool used[MAXN]; // 已經使用過的圖（已經确定最短距離的點）
int V; // 點的個數

void Dijkstra(int s)
{
    priority_queue<P,vector<P>, greater<P> > que; // 定義一個堆 從按最短距離小到的大排
    fill(d,d+V,INF);
    d[s] = 0;
    que.push(P(0,s));
    while(!que.empty()) // 為空就說明所有節點都已經用過
    {
        P temp = que.top(); que.pop();
        int v = temp.second;
        if(d[v] < temp.first) continue; // 沒必要更新了
        for(int i = 0;i < G[v].size();i++)
        {
            edge e = G[v][i];
            if(d[e.to] > d[v]+e.cost)
            {
                d[e.to] = d[v]+e.cost;
                que.push(P(d[e.to],e.to));
            }
        }
    }
}

Floyd-Warshall

Floyd算法簡單暴力，主要用于求多源最短路徑（任意兩個點的最短路徑）

核心代碼十分短小精悍

int d[MAXN][MAXN]; // d[u][v] 表示從u -> v的權值 不存在的時候為0
int V; // 頂點個數

void Floyd()
{
    for(int k = 0;k < V;k++)
        for(int i = 0;i < V;i++)
            for(int j = 0;j < V;j++)
                d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
}

十分暴力複雜度可想而知O(V3)

那麼這幾行代碼是什麼意思呢？這其實還是DP

我們用d[k+1][i][j] 來表示隻使用0~k和i,j頂點的情況下的最短路

初始狀态為d[0][i][j] = cost[i][j] 是以我們可以得到下面這個式子：

d [ k ] [ i ] [ j ] = { d [ k − 1 ] [ i ] [ j ] 　 ( 不經過點 K ) d [ k − 1 ] [ i ] [ k ] + d [ k − 1 ] [ k ] [ j ] 　（經過 K 點）　＝　 m i n ( d [ k − 1 ] [ i ] [ j ] , d [ k − 1 ] [ i ] [ k ] + d [ k − 1 ] [ k ] [ j ] ) d[k][i][j] = \begin{cases} d[k-1][i][j] 　(不經過點K)\\ d[k-1][i][k] + d[k-1][k][j]　（經過K點）\\ \end{cases}　＝　min(d[k-1][i][j],d[k-1][i][k] + d[k-1][k][j]) d[k][i][j]={d[k−1][i][j]　(不經過點K)d[k−1][i][k]+d[k−1][k][j]　（經過K點）　＝　min(d[k−1][i][j],d[k−1][i][k]+d[k−1][k][j])

當然我們可以稍微優化一下，時間以及到極限了，我們可以想辦法把空間複雜度降下來

也就是我們上面那個形式，也就是為什麼K必須放在最外面的原因

我們觀察三維的那個式子與K相關的就隻有K與K-1是以我們可以進行降維操作

也就是當K=s的時候，在執行狀态壓縮之前d[i][j]的值存都是的d[k-1][i][j]

也就是将上一個狀态動态儲存起來了是以才有上面的簡短的代碼

路徑還原

最後的問題就是當我們知道最短路徑多少的時候，難免有時候需要知道該怎麼走才有這條最短路徑呢

用 Dijkstra來示範路徑還原其他的算法也都可以用這個來解決

在此算法中滿足 d[j] = d[k] + cost[k][j]的點K我們稱為j的前驅結點，也就是在到j之前必須經過點K

我們用一個數組prev來存相應節點的前驅結點，不斷尋找前驅結點就可以找到最短路了，不過這是從後往前找

最後需要反轉一下得到最後的答案。

示例代碼如下：注意第25行

int cost[MAXN][MAXN]; // cost[i][j] 表示從i到j之間的權值（不存在是為INF）
int d[MAXN]; // 從起點到其他點的最短距離
bool used[MAXN]; // 已經使用過的圖（已經确定最短距離的點）
int V; // 點的個數
int prev[MAXN];

void Dijkstra(int s)
{
    fill(d,d+V,INF); // algorithm中的函數 将d數組全部賦為INF
    fill(used,used+V,false);
    fill(prev,prev+V,-1); // -1表示到頭了 即沒有前驅結點
    d[s] = 0;
    
    while(true)    
    {
        int v = -1;
        // c從未使用過的點集中取一個距離最小的點
        for(int u = 0;u < V;u++)
        	if(!used[u] && (v == -1 || d[u] < d[v])) v = u;
        if(v == -1) break; // 所有的點的最短路徑确定則退出
       	used[v] = true;
        for(int u = 0;u < V;u++)
        {
            d[u] = min(d[u],d[v]+cost[v][u]);
            prev[u] = v; 
        }
    }
}

// 到頂點t的最短路
vector<int> get_path(int t) 
{
    vector<int> path;
    for(; t != -1;t = prev[t]) path.push_pack(t);
    reverse(path.begin(),path.end());
    return path;
}

The end !!!

圖的最短路徑的三種算法Bellman-Ford Dijkstra Floyd及其了解最短路徑的三種算法以及路徑還原與負圈判斷

最短路徑的三種算法以及路徑還原與負圈判斷

Bellman-Ford

負圈的判斷

Dijkstra

簡單的優化

Floyd-Warshall

路徑還原

繼續閱讀

hdu2066 一個人的旅行

【HDU 3499】 Flight 最短路分層圖 Dijkstra堆優化前向星

POJ -- 2387 Til the Cows Come Home

SPFA算法模闆(實際上是bellman-ford) 的隊列優化

Floyd-Warshall Algorithm

POJ 3259——Wormholes 圖論

neo4j使用cypher求多個結點兩兩間的最短路徑

vc6 運作庫的bug---C++程式穩定運作一段時間後異常中止

程式設計－從矩陣左上角走到右下角

poj 2457 Part Acquisition最短路徑dijikstra迪傑斯特拉

資料結構學習筆記——圖的應用（最短路徑和關鍵路徑）

城市間緊急救援(Dijkstra算法)

迷宮最短路徑問題

bellman -ford算法的改進 spfa 算法

最短路徑->Dijkstra算法和Floyd算法

【TSP-GA】基于MATLAB的TSP-GA問題優化仿真