Dijkstra算法--單源最短路徑

2019-11-11 01:56:02

字體：大中小

供稿：網(wǎng)友

在http://blog.csdn.net/hacker_zhidian/article/details/54898064這一篇博客中總結(jié)了一下在求圖的最短路中的一個(gè)算法-Floyd算法，F(xiàn)loyd算法用于求圖的多源最短路徑（多源最短路徑：圖的所有頂點(diǎn)到其他頂點(diǎn)的最短路徑），時(shí)間復(fù)雜度和其他求最短路算法相比較高，如果一些題目只要求求單源最短路徑（單源最短路徑：圖的某個(gè)頂點(diǎn)到其他頂點(diǎn)的最短路徑）的話，F(xiàn)loyd算法顯然不是最好的選擇，那么今天我們來看一下另一個(gè)用于求單源最短路徑的算法：Dijkstra算法。

首先我們來看一個(gè)圖：這里寫圖片描述圖中共有A、B、C、D四個(gè)頂點(diǎn)，五條邊，假設(shè)我們現(xiàn)在要求頂點(diǎn)B到其他頂點(diǎn)的最短路徑，依據(jù)Dijkstra算法的原理：

首先我們先找到距離頂點(diǎn)B路徑最短的頂點(diǎn)，在這個(gè)圖中很明顯距離頂點(diǎn)B路徑最短的點(diǎn)為頂點(diǎn)D。之后，將頂點(diǎn)D做上訪問標(biāo)記，并對(duì)圖中的所有頂點(diǎn)進(jìn)行檢測(cè)，看看能否通過頂點(diǎn)D來縮短頂點(diǎn)B到其他頂點(diǎn)的路徑。很明顯，B–>D–>C（路徑為3）這條路的路徑小于B–>C（路徑為6）這條路的路徑，那么我們更新從頂點(diǎn)B到頂點(diǎn)C的最短路徑，頂點(diǎn)D的試探結(jié)束。我們可以將這個(gè)過程稱為“縮放”，現(xiàn)在，頂點(diǎn)D的“縮放”結(jié)束。之后我們繼續(xù)尋找距離頂點(diǎn)B路徑最短并且沒有被標(biāo)記的頂點(diǎn)，現(xiàn)在距離頂點(diǎn)B路徑最短并且沒有被標(biāo)記的頂點(diǎn)為頂點(diǎn)C（頂點(diǎn)D已經(jīng)被標(biāo)記了），同樣的重復(fù)“縮放”過程，直到圖中所有的頂點(diǎn)都被標(biāo)記。

理解了上面的過程，我們就可以架構(gòu)出大概的Dijkstra算法的代碼了：

/** n 代表圖的頂點(diǎn)總數(shù)* e[][] 代表圖的鄰接矩陣儲(chǔ)存* book[] 代表標(biāo)記數(shù)組，標(biāo)記頂點(diǎn)是否已經(jīng)被選擇過* dis[] 數(shù)組儲(chǔ)存的是源點(diǎn)距離其他頂點(diǎn)的最短路徑*/for(int i = 1; i <= n - 1; i++) // 對(duì)除了頂點(diǎn)B以外的所有頂點(diǎn)進(jìn)行“縮放”，所以是n-1次頂點(diǎn)縮放{ int min = inf; // inf 為無窮大 int u; // u為當(dāng)前距離頂點(diǎn)B路徑最短的頂點(diǎn) for(int j = 1; j <= n; j++) // 找到距離頂點(diǎn)B最短的頂點(diǎn) { if(book[j] == 0 && dis[j] < min) { min = dis[j]; u = j; } } book[u] = 1; // 對(duì)要縮放的頂點(diǎn)進(jìn)行標(biāo)記 for(int k = 1; k <= n; k++) // 對(duì)這個(gè)距離頂點(diǎn)B最短的頂點(diǎn)進(jìn)行縮放 { if(e[u][k] < inf) { if(dis[k] > dis[u] + e[u][k]) { dis[k] = dis[u] + e[u][k]; // 如果確實(shí)可以通過這個(gè)頂點(diǎn)的縮放來縮短最短路徑，那么更新最短路徑 } } }}

Ok，算法的核心代碼就是這些了，下面給出這個(gè)例子的完整代碼：

/** n 代表圖的頂點(diǎn)總數(shù)* e[][] 代表圖的鄰接矩陣儲(chǔ)存* book[] 代表標(biāo)記數(shù)組，標(biāo)記頂點(diǎn)是否已經(jīng)被選擇過* dis[] 數(shù)組儲(chǔ)存的是源點(diǎn)距離其他頂點(diǎn)的最短路徑*/#include <iostream>using namespace std;const int N = 500;const int inf = 999999999;int e[N][N];int book[N];int dis[N];int main(){ int n, m, s; // 圖的頂點(diǎn)總數(shù)、邊的總數(shù)和源節(jié)點(diǎn) cin >> n >> m>> s; for(int i = 1; i <= n; i++) { dis[i] = inf; // 初始化dis數(shù)組 for(int j = 1; j <= n; j++) { if(i == j) { e[i][j] = 0; } else { e[i][j] = inf; } } } int x, y, w; // 邊的信息 for(int i = 1; i <= m; i++) // 輸入邊 { cin >> x >> y >> w; e[x][y] = e[y][x] = w; } dis[s] = 0; for(int i = 1; i <= n - 1; i++) // 對(duì)除了源點(diǎn)以外的所有頂點(diǎn)進(jìn)行“縮放”，所以是n-1次頂點(diǎn)縮放 { int min = inf; // inf 為無窮大 int u; // u為當(dāng)前距離源點(diǎn)路徑最短的頂點(diǎn) for(int j = 1; j <= n; j++) // 找到距離源點(diǎn)最短的頂點(diǎn) { if(book[j] == 0 && dis[j] < min) { min = dis[j]; u = j; } } book[u] = 1; // 對(duì)要縮放的頂點(diǎn)進(jìn)行標(biāo)記 for(int k = 1; k <= n; k++) // 對(duì)這個(gè)距離源點(diǎn)最短的頂點(diǎn)進(jìn)行縮放 { if(e[u][k] < inf) { if(dis[k] > dis[u] + e[u][k]) { dis[k] = dis[u] + e[u][k]; // 如果確實(shí)可以通過這個(gè)頂點(diǎn)的縮放來縮短最短路徑，那么更新最短路徑 } } } } for(int i = 1; i <= n; i++) // 輸出源點(diǎn)到其他頂點(diǎn)的最短路徑 { cout.width(-5); cout << dis[i] << " "; } cout << endl; return 0;}

接下來，我們將給出的例圖中的數(shù)據(jù)輸入并運(yùn)行程序：這里寫圖片描述和預(yù)想的一樣，小伙伴們可以自己嘗試一下。在這里，Dijkstra算法的時(shí)間復(fù)雜度為O(N^2)，確實(shí)比Floyd算法小。當(dāng)然，還有一點(diǎn)要注意，Dijkstra算法是不能解決具有負(fù)權(quán)邊的圖的。如果博客中有什么不正確的地方，還請(qǐng)多多指點(diǎn)。謝謝觀看。。。