單源最短路徑問(wèn)題--Dijkstra算法和Floyd算法

2019-11-09 19:45:12

字體：大中小

供稿：網(wǎng)友

昨天復(fù)習(xí)了一下單源最短路徑問(wèn)題，今天總結(jié)一下。

解決單源最短路徑問(wèn)題，我們熟知的算法首先就是Dijkstra算法了。Dijkstra算法的核心就是貪心思想。我在以前的博客中也寫(xiě)過(guò)這個(gè)算法：圖的拓?fù)渑判颉㈥P(guān)鍵路徑、最短路徑算法 – C++實(shí)現(xiàn)，現(xiàn)在看以前的博客，我的代碼思路還是很清晰的。Dijkstra算法可以求出某一點(diǎn)到其他所有點(diǎn)的最短路徑，本文還將介紹一種可求出所有點(diǎn)對(duì)的最短路徑的算法——Floyd算法。

Dijkstra算法

Dijkstra算法是典型的單源最短路徑算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，知道擴(kuò)展到終點(diǎn)為之。Dijkstra算法的要求是圖中不存在負(fù)權(quán)邊。因?yàn)镈ijkstra算法基于貪心策略，它是短視的。如果存在某個(gè)路徑上有負(fù)權(quán)邊，可能繞了幾圈得到的結(jié)果甚至是更優(yōu)的，所以Dijkstra算法在有負(fù)權(quán)邊的圖應(yīng)用上是失敗的。

Dijkstra算法的具體解釋我就不說(shuō)了，如果不明白概念可參考這篇博客的概念解釋?zhuān)鹤疃搪窂健狣ijkstra算法和Floyd算法。

本文所有測(cè)試用例所用graph就是下面這幅圖片中的graph：

下面給出我的代碼：

#include <iostream>#include <vector>#include <iomanip>#include <limits.h>const int NUM_VERTICES = 5; //A B C D Evoid PRint_solution(std::vector<int>& dist, std::vector<int>& path){ for(auto i : dist) std::cout<<std::setw(3)<<i<<' '; std::cout<<std::endl; for(auto i : path) std::cout<<std::setw(3)<<i<<' '; std::cout<<std::endl;}void dijkstra(std::vector<std::vector<int>>& graph, int source){ std::vector<int> dist(NUM_VERTICES, 0), path(NUM_VERTICES, -1); for(int i=1; i<NUM_VERTICES; ++i){ dist[i] = graph[source][i] == 0 ? INT_MAX : graph[source][i]; path[i] = source; } std::vector<bool> visited(NUM_VERTICES, false); visited[source] = true; for(int i=0; i<NUM_VERTICES-1; ++i){ int min = INT_MAX; int min_index = -1; for(int j=0; j<NUM_VERTICES; ++j){ if(!visited[j] && dist[j] < min){ min = dist[j]; min_index = j; } } visited[min_index] = true; for(int k=0; k<NUM_VERTICES; ++k){ int weight = graph[min_index][k] == 0 ? INT_MAX : graph[min_index][k]; if(!visited[k] && weight != INT_MAX && dist[min_index] != INT_MAX && dist[min_index]+weight < dist[k]){ dist[k] = dist[min_index] + weight; path[k] = min_index; } } } print_solution(dist, path);}int main(){ std::vector<std::vector<int>> graph = {{0, 10, 0, 30, 100}, //A {0, 0, 50, 0, 0 }, //B {0, 0, 0, 0, 10 }, //C {0, 0, 20, 0, 60 }, //D {0, 0, 0, 0, 0 }};//E // A B C D E dijkstra(graph, 0); //param 0 means vertex 'A' return 0;}

輸出結(jié)果：這里寫(xiě)圖片描述

Dijkstra算法的時(shí)間復(fù)雜度是O(|E|+|V|2|)=O(V2) $O(|E|+|V|^2|) = O(V^2)$ （參考：Dijkstra算法時(shí)間復(fù)雜度）。對(duì)于稠密的圖來(lái)說(shuō)，|E| 就是|V|^2，所以Dijsstra算法中遍歷dist[min_index]+weigth那個(gè)循環(huán)加上最外層循環(huán)時(shí)間復(fù)雜度為θ(|V|2) $θ(|V|^2)$ ，對(duì)于稠密圖，這就是最優(yōu)的了，總的時(shí)間復(fù)雜度正好是θ(|E|+|V|2)=θ(|V|2+|V|2)=O(|V|2) $θ(|E|+|V|^2) = θ(|V|^2+|V|^2) = O(|V|^2)$ 。但是對(duì)于非稠密圖，這個(gè) |E| 實(shí)際沒(méi)這么大，甚至 |E|=|V| $|E| = |V|$ ，這個(gè)算法就未免效率低下了。

優(yōu)化法方法是使用最小堆，我們dist[min_Index]+weight小于dist[k]時(shí)，將新的dist[k]的值插入最小堆；在上面查找最小值的操作中，每次從最小堆中取出最小值，并且檢查是否visited，如果沒(méi)visited，那就找到新的頂點(diǎn)了。改進(jìn)后的算法時(shí)間復(fù)雜度是O(|E|lg|V|) $O(|E|lg|V|)$ 。

Floyd算法

Floyd算法是解決任意兩點(diǎn)間最短路徑的一種算法，可以正確處理負(fù)權(quán)圖的最短路徑問(wèn)題。

上面的Dijkstra算法求出了某個(gè)點(diǎn)到其他所有點(diǎn)的最短路徑，我們要求所有點(diǎn)對(duì)的最短路徑，有這樣一種思路，就是再外面再循環(huán) |V| 次，那么不就求出所由點(diǎn)對(duì)的最短路徑了嗎？時(shí)間復(fù)雜度為O(N3) $O(N^3)$ 。

不過(guò)，Dijkstra算法為我們提供了一種動(dòng)態(tài)規(guī)劃的思想，一個(gè)點(diǎn)到另外一個(gè)點(diǎn)的最短路徑，要么直接到達(dá)就是最短的，要么就是經(jīng)過(guò)了一個(gè)已經(jīng)最優(yōu)化的點(diǎn)間接到達(dá)這個(gè)點(diǎn)就是最短的，只有這么兩種情況。Floyd算法就根據(jù)這個(gè)思路把所有情況同過(guò)DP表的方式計(jì)算出來(lái)，時(shí)間復(fù)雜度是一樣的，也是O(N3) $O(N^3)$ ，不過(guò)Floyd算法簡(jiǎn)潔的多。

Floyd算法DP公式：

D0[V][W]=min{D?1[V][W],D?1[V][K]+D?1[K][W]} $D^0[V][W]=min/{ D^-1[V][W], D^-1[V][K]+D^-1[K][W]/}$

D是一個(gè)二維矩陣，是一個(gè)輔助矩陣，初始狀態(tài)和graph是一致的，通過(guò)該矩陣的變化，我們來(lái)修正path矩陣的值即可。

更多的關(guān)于Floyd算法的解釋參見(jiàn)：數(shù)據(jù)結(jié)構(gòu)之最短路徑（Floyd），包括我下面用的打印函數(shù)，可以參見(jiàn)它的解釋。不過(guò)它的打印函數(shù)對(duì)于非強(qiáng)連通圖有一點(diǎn)問(wèn)題，我加以修正了。

打印函數(shù)實(shí)際上意思就是，比如我要找(0, 8)的最短路徑，如果path[0][8]的值為k，說(shuō)明0->8之間經(jīng)過(guò)路徑k，且0->k的結(jié)果是最優(yōu)的，所以目前找到了所求路徑的一部分{0, k1}。然后我們?cè)俅尾檎?k, 8)的最短路徑，看它們兩之間有沒(méi)有中間更優(yōu)化的路徑，比如找到，如果有，那就找到了路徑{0, k1, k2}，依次下去，知道path[k][8]的結(jié)果為8，說(shuō)明沒(méi)有了。總的路徑就是{0, k1, k2 … 8}。

下面給出我的代碼：

#include <iostream>#include <vector>#include <iomanip>#include <limits.h>const int NUM_VERTICES = 5; //A B C D Evoid print_solution(std::vector<std::vector<int>>& helper, std::vector<std::vector<int>>& path){ for(int i=0; i<NUM_VERTICES; ++i){ for(int j=i+1; j<NUM_VERTICES; ++j){ if(helper[i][j] == INT_MAX) continue; std::cout<<i<<"->"; int k = path[i][j]; while(k != j){ std::cout<<k<<"->"; k = path[k][j]; } std::cout<<j<<std::endl; } }}void floyd(std::vector<std::vector<int>>& graph){ std::vector<std::vector<int>> helper(NUM_VERTICES, std::vector<int>(NUM_VERTICES)), path(NUM_VERTICES, std::vector<int>(NUM_VERTICES)); for(int i=0; i<NUM_VERTICES; ++i){ for(int j=0; j<NUM_VERTICES; ++j){ helper[i][j] = graph[i][j] == 0 ? INT_MAX : graph[i][j]; path[i][j] = j; } } for(int k=0; k<NUM_VERTICES; ++k){ for(int i=0; i<NUM_VERTICES; ++i){ for(int j=0; j<NUM_VERTICES; ++j){ if(helper[i][k] != INT_MAX && helper[k][j] != INT_MAX && helper[i][j] > helper[i][k] + helper[k][j]){ helper[i][j] = helper[i][k] + helper[k][j]; path[i][j] = k; } } } } print_solution(helper, path);}int main(){ std::vector<std::vector<int>> graph = {{0, 10, 0, 30, 100}, //A {0, 0, 50, 0, 0 }, //B {0, 0, 0, 0, 10 }, //C {0, 0, 20, 0, 60 }, //D {0, 0, 0, 0, 0 }};//E // A B C D E floyd(graph); //param 0 means vertex 'A' return 0;}

輸出結(jié)果：這里寫(xiě)圖片描述