在http://blog.csdn.net/hacker_zhidian/article/details/54898064這一篇博客中總結(jié)了一下在求圖的最短路中的一個算法-Floyd算法，F(xiàn)loyd算法用于求圖的多源最短路徑（多源最短路徑：圖的所有頂點到其他頂點的最短路徑），時間復雜度和其他求最短路算法相比較高，如果一些題目只要求求單源最短路徑（單源最短路徑：圖的某個頂點到其他頂點的最短路徑）的話，F(xiàn)loyd算法顯然不是最好的選擇，那么今天我們來看一下另一個用于求單源最短路徑的算法：Dijkstra算法。
首先我們來看一個圖： 
圖中共有A、B、C、D四個頂點，五條邊，假設我們現(xiàn)在要求頂點B到其他頂點的最短路徑，依據(jù)Dijkstra算法的原理：
首先我們先找到距離頂點B路徑最短的頂點，在這個圖中很明顯距離頂點B路徑最短的點為頂點D。之后，將頂點D做上訪問標記，并對圖中的所有頂點進行檢測，看看能否通過頂點D來縮短頂點B到其他頂點的路徑。很明顯，B–>D–>C（路徑為3）這條路的路徑小于B–>C（路徑為6）這條路的路徑，那么我們更新從頂點B到頂點C的最短路徑，頂點D的試探結(jié)束。我們可以將這個過程稱為“縮放”，現(xiàn)在，頂點D的“縮放”結(jié)束。之后我們繼續(xù)尋找距離頂點B路徑最短并且沒有被標記的頂點，現(xiàn)在距離頂點B路徑最短并且沒有被標記的頂點為頂點C（頂點D已經(jīng)被標記了），同樣的重復“縮放”過程，直到圖中所有的頂點都被標記。
理解了上面的過程，我們就可以架構(gòu)出大概的Dijkstra算法的代碼了：
/** n 代表圖的頂點總數(shù)* e[][] 代表圖的鄰接矩陣儲存* book[] 代表標記數(shù)組，標記頂點是否已經(jīng)被選擇過* dis[] 數(shù)組儲存的是源點距離其他頂點的最短路徑*/for(int i = 1; i <= n - 1; i++) // 對除了頂點B以外的所有頂點進行“縮放”，所以是n-1次頂點縮放{ int min = inf; // inf 為無窮大 int u; // u為當前距離頂點B路徑最短的頂點 for(int j = 1; j <= n; j++) // 找到距離頂點B最短的頂點 { if(book[j] == 0 && dis[j] < min) { min = dis[j]; u = j; } } book[u] = 1; // 對要縮放的頂點進行標記 for(int k = 1; k <= n; k++) // 對這個距離頂點B最短的頂點進行縮放 { if(e[u][k] < inf) { if(dis[k] > dis[u] + e[u][k]) { dis[k] = dis[u] + e[u][k]; // 如果確實可以通過這個頂點的縮放來縮短最短路徑，那么更新最短路徑 } } }}Ok，算法的核心代碼就是這些了，下面給出這個例子的完整代碼：
/** n 代表圖的頂點總數(shù)* e[][] 代表圖的鄰接矩陣儲存* book[] 代表標記數(shù)組，標記頂點是否已經(jīng)被選擇過* dis[] 數(shù)組儲存的是源點距離其他頂點的最短路徑*/#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; // 圖的頂點總數(shù)、邊的總數(shù)和源節(jié)點 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++) // 對除了源點以外的所有頂點進行“縮放”，所以是n-1次頂點縮放 { int min = inf; // inf 為無窮大 int u; // u為當前距離源點路徑最短的頂點 for(int j = 1; j <= n; j++) // 找到距離源點最短的頂點 { if(book[j] == 0 && dis[j] < min) { min = dis[j]; u = j; } } book[u] = 1; // 對要縮放的頂點進行標記 for(int k = 1; k <= n; k++) // 對這個距離源點最短的頂點進行縮放 { if(e[u][k] < inf) { if(dis[k] > dis[u] + e[u][k]) { dis[k] = dis[u] + e[u][k]; // 如果確實可以通過這個頂點的縮放來縮短最短路徑，那么更新最短路徑 } } } } for(int i = 1; i <= n; i++) // 輸出源點到其他頂點的最短路徑 { cout.width(-5); cout << dis[i] << " "; } cout << endl; return 0;}接下來，我們將給出的例圖中的數(shù)據(jù)輸入并運行程序： 
和預想的一樣，小伙伴們可以自己嘗試一下。 在這里，Dijkstra算法的時間復雜度為O(N^2)，確實比Floyd算法小。當然，還有一點要注意，Dijkstra算法是不能解決具有負權(quán)邊的圖的。 如果博客中有什么不正確的地方，還請多多指點。 謝謝觀看。。。
新聞熱點
疑難解答
