Floyd算法--多源最短路徑

2019-11-11 03:52:01

字體：大中小

供稿：網(wǎng)友

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

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

這里寫圖片描述

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

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

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

對于上面的代碼，其實當(dāng)i等于1的時候是沒有意義的：頂點A借助頂點A來嘗試是否能使得頂點A到頂點B的最短路徑變短（自己借助自己有什么意義呢），不過我們這里的重點并不在這，那么現(xià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]; } } }}

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

下面給出完整的Floyd代碼：

#include <iostream>using namespace std;const int inf = 999999999; // 模擬無窮大（表示圖的兩個頂點沒有直接相連）const int N = 1000; // 圖的頂點個數(shù)最多為1000個int e[N][N]; // 圖的鄰接矩陣int main(){ int n, m; // 圖的頂點個數(shù)和邊的條數(shù)(其實叫度的數(shù)目會更好) 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ù)，運行結(jié)果：這里寫圖片描述 Yes，完成，我們可以檢驗一下圖中的數(shù)據(jù)是否符合，確實是圖中所有兩個頂點之間的最短路徑。各位小伙伴可以自行檢驗一下。那么Floyd算法的時間復(fù)雜度呢，在這個代碼中算法的時間復(fù)雜度是O(N^3)，相比其他最短路算法，還是比較高的，但是這個算法可以求多源最短路徑，而且代碼相對簡單，所以這個算法還是較優(yōu)的。如果博客中有什么不正確的地方，還請多多指點。謝謝觀看。。。