Floyd算法--多源最短路徑

2019-11-11 03:19:03

字體：大中小

供稿：網(wǎng)友

在一個(gè)給定的圖中求兩個(gè)頂點(diǎn)的最短路徑的算法一直是比較常用和比較重要的算法。主要的求最短路徑的算法有Floyd算法、Dijkstra算法和Bellman-Ford算法等等，本篇我們先來看一下Floyd算法：

首先我們知道，要求一個(gè)圖中兩個(gè)頂點(diǎn)中的最短路徑，除了計(jì)算出這兩個(gè)頂點(diǎn)的直接路徑，還可以借助其他的頂點(diǎn)作為“跳板”，來看看能不能使得這兩點(diǎn)的路徑變短，來看一個(gè)例子：

這里寫圖片描述

假設(shè)這是一個(gè)給定的無向圖圖（畫的不好，大家多多擔(dān)待），圖中共有4個(gè)頂點(diǎn)（A、B、C、D），圖中的邊共有：A-->B(10)、A-->C(2)、C-->B(6)、C-->D(1)、D-->B(2)五條邊（嚴(yán)格來說有10條邊，因?yàn)槭菬o向圖），如果我們要求頂點(diǎn)A和頂點(diǎn)B的最短路徑該怎么辦呢，明顯：頂點(diǎn)A和頂點(diǎn)B直接相連，距離為10，然而我們注意到頂點(diǎn)A和頂點(diǎn)C相連，頂點(diǎn)C和頂點(diǎn)B相連：A-->C-->B的距離一共是8，明顯比頂點(diǎn)A直接到頂點(diǎn)B更短。再觀察一下，我們還可以發(fā)現(xiàn)頂點(diǎn)C和頂點(diǎn)D直接相連，D頂點(diǎn)和頂點(diǎn)B直接相連：A-->C-->D-->B的距離一共是5，又是一條更短的路徑！之后我們找不到頂點(diǎn)A到頂點(diǎn)B還有比距離5更短的路徑了，那么，在這個(gè)圖中頂點(diǎn)A到頂點(diǎn)B的最短路徑就是5

在上面的那個(gè)簡(jiǎn)單的例子中，求頂點(diǎn)A到頂點(diǎn)B的最短路徑，我們正是利用了其他的頂點(diǎn)作為“跳板”，來尋找是否有更短的路徑，F(xiàn)loyd算法的核心思想也正是這個(gè)：借助圖的其它頂點(diǎn)來求目標(biāo)頂點(diǎn)之間的最短路徑 對(duì)于上面的例子，假設(shè)頂點(diǎn)A為1號(hào)頂點(diǎn)，頂點(diǎn)B為2號(hào)頂點(diǎn)，頂點(diǎn)的總數(shù)為n，e[n][n]為圖的鄰接矩陣。那么我們可以用代碼來描述剛剛的過程：

for(int i = 1; i <= n; i++){ if(e[1][2] > e[1][i] + e[i][2]) { /* 這段代碼的意思是：循環(huán)遍歷圖中的所有頂點(diǎn) * 如果利用圖中的其它頂點(diǎn)可以使得頂點(diǎn)A到頂點(diǎn)B的路徑變短， * 那么更新頂點(diǎn)A到頂點(diǎn)B的最短路徑 */ e[1][2] = e[1][i] + e[i][2]; }}

對(duì)于上面的代碼，其實(shí)當(dāng)i等于1的時(shí)候是沒有意義的：頂點(diǎn)A借助頂點(diǎn)A來嘗試是否能使得頂點(diǎn)A到頂點(diǎn)B的最短路徑變短（自己借助自己有什么意義呢），不過我們這里的重點(diǎn)并不在這，那么現(xiàn)在我們要求圖中的所有頂點(diǎn)到其他頂點(diǎn)的最短路徑該怎么辦呢，按照剛剛的思路，我們可以大概的寫出代碼：

for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++) { for(int k = 1; k <= n; k++) { if(e[j][k] > e[j][i] + e[i][k]) { e[j][k] = e[j][i] + e[i][k]; } } }}

其實(shí)很好理解，就是在原來的基礎(chǔ)上嵌套了一個(gè)雙重循環(huán)，這個(gè)雙重循環(huán)是為了遍歷圖中的任意兩個(gè)頂點(diǎn)，然后再利用最外面的一重循環(huán)來尋找最短路徑，整個(gè)代碼理解起來就是：借助前 i 個(gè)頂點(diǎn)來尋找圖中的任意兩個(gè)定點(diǎn)的最短路徑。 Ok，其實(shí)這就是Floyd算法的核心代碼，如果你把不需要的大括號(hào)去掉（這里只是為了代碼美觀），你會(huì)發(fā)現(xiàn)這個(gè)算法只有5行！

下面給出完整的Floyd代碼：

#include <iostream>using namespace std;const int inf = 999999999; // 模擬無窮大（表示圖的兩個(gè)頂點(diǎn)沒有直接相連）const int N = 1000; // 圖的頂點(diǎn)個(gè)數(shù)最多為1000個(gè)int e[N][N]; // 圖的鄰接矩陣int main(){ int n, m; // 圖的頂點(diǎn)個(gè)數(shù)和邊的條數(shù)(其實(shí)叫度的數(shù)目會(huì)更好) cin >> n >> m; for(int i = 1; i <= n; i++) // 初始化圖 { 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; } for(int i = 1; i <= n; i++) // Floyd算法核心代碼 { for(int j = 1; j <= n; j++) { for(int k = 1; k <= n; k++) { if(e[j][k] > e[j][i] + e[i][k]) { e[j][k] = e[j][i] + e[i][k]; } } } } for(int i = 1; i <= n; i++) // 輸出算法結(jié)束后的圖的鄰接矩陣信息 { for(int j = 1; j <= n; j++) { cout.width(4); cout << e[i][j] << " "; } cout << endl; } return 0;}

輸入我們上面的例子數(shù)據(jù)，運(yùn)行結(jié)果：這里寫圖片描述 Yes，完成，我們可以檢驗(yàn)一下圖中的數(shù)據(jù)是否符合，確實(shí)是圖中所有兩個(gè)頂點(diǎn)之間的最短路徑。各位小伙伴可以自行檢驗(yàn)一下。那么Floyd算法的時(shí)間復(fù)雜度呢，在這個(gè)代碼中算法的時(shí)間復(fù)雜度是O(N^3)，相比其他最短路算法，還是比較高的，但是這個(gè)算法可以求多源最短路徑，而且代碼相對(duì)簡(jiǎn)單，所以這個(gè)算法還是較優(yōu)的。如果博客中有什么不正確的地方，還請(qǐng)多多指點(diǎn)。謝謝觀看。。。