通常，數組用循環來處理，一般來說，一維數組的數據處理可以使用單重循環或雙重循環。如輸出數組元素值，從一個數組中挑選最大值或最小值等可以使用單重循環。而對于數組的排序一般使用雙重循環，因為單重循環可以挑出一個元素的最大值或最小值，而有n個元素的數組則通過n次挑選便可完成整個數組的排序，所以在單重循環外再嵌套一個循環即可。

對于二維數組的數據處理，通常可以使用雙重循環或三重循環，如二維數組元素值的輸出，便可以使用雙重循環，而矩陣（二維數組）乘法，便可以使用三重循環：

const int maxn=105; int a[maxn][maxn],b[maxn][maxn]; int ans[maxn][maxn]; int a_n,a_m,b_n,b_m; void mul(){ for(int i=0; i<a_m; i ){ // i循環數組a的行 for(int j=0; j<b_n; j ){// j循環數組b的列 for(int k=0; k<a_n; k ){ // k循環數組a的列，數組b的行， ans[i][j] =a[i][k]*b[k][j]; } } }

三重循環的另一個經典應用就是Floyd算法求多源最短路徑。

Floyd算法又稱為插點法，是一種利用動态規劃的思想尋找給定的加權圖中多源點之間最短路徑的算法，與Dijkstra算法類似。該算法名稱以創始人之一、1978年圖靈獎獲得者、斯坦福大學計算機科學系教授羅伯特·弗洛伊德命名。

其算法的核心是在頂點 i 和頂點 j 之間，插入頂點k，看是否能夠縮短 i 和 j 之間的距離（松馳操作）。

暑假，小哼準備去一些城市旅遊。有些城市之間有公路，有些城市之間則沒有，如下圖。為了節省經費以及方便計劃旅程，小哼希望在出發之前知道任意兩個城市之前的最短路程。

可以畫成如下的簡圖↓

上圖中有4個城市8條公路，公路上的數字表示這條公路的長短。請注意這些公路是單向的。我們現在需要求任意兩個城市之間的最短路程，也就是求任意兩個點之間的最短路徑。這個問題這也被稱為“多源最短路徑”問題。

現在需要一個數據結構來存儲圖的信息，我們可以用一個4*4的矩陣（二維數組e）來存儲。比如1号城市到2号城市的路程為2，則設e[1][2]的值為2。2号城市無法到達4号城市，則設置e[2][4]的值為∞。另外此處約定一個城市自己是到自己的也是0，例如e[1][1]為0，具體如下↓

現在回到問題，如何求任意兩點之間最短路徑呢？

我們來想一想，從a到b，直接相連（到達）不一定是最短的，如果經過第三個點（頂點k），并通過這個頂點k中轉即a->k->b，有可能是從頂點a點到頂點b的最短路程。那麼這個中轉的頂點k是1~n中的哪個點呢？甚至有時候不隻通過一個點，而是經過兩個點或者更多點中轉會更短，即a→k1→k2→b或者a→k1→k2→…→ki→b。

比如上圖中從4号城市到3号城市（4→3）的鄰接路程e[4][3]原本是12。如果隻通過1号城市中轉（4→1→3），路程将縮短為11（e[4][1] e[1][3]=5 6=11）。其實1号城市到3号城市也可以通過2号城市中轉，使得1号到3号城市的路程縮短為5（e[1][2] e[2][3]=2 3=5）。所以如果同時經過1号和2号兩個城市中轉的話，從4号城市到3号城市的路程會進一步縮短為10。通過這個的例子，我們發現每個頂點都有可能使得另外兩個頂點之間的路程變短。好，下面我們将這個問題一般化。

當任意兩點之間不允許經過第三個點時，這些城市之間最短路程就是初始路程，如下↓

如現在隻允許經過1号頂點，求任意兩點之間的最短路程，應該如何求呢？隻需判斷e[i][1] e[1][j]是否比e[i][j]要小即可。e[i][j]表示的是從i号頂點到j号頂點之間的路程。e[i][1] e[1][j]表示的是從i号頂點先到1号頂點，再從1号頂點到j号頂點的路程之和。其中i是1~n循環，j也是1~n循環，代碼實現如下↓

在隻允許經過1号頂點的情況下，任意兩點之間的最短路程更新為↓

通過上圖我們發現：在隻通過1号頂點中轉的情況下，3号頂點到2号頂點（e[3][2]）、4号頂點到2号頂點（e[4][2]）以及4号頂點到3号頂點（e[4][3]）的路程都變短了。

接下來繼續求在隻允許經過1和2号兩個頂點的情況下任意兩點之間的最短路程。如何做呢？我們需要在隻允許經過1号頂點時任意兩點的最短路程的結果下，再判斷如果經過2号頂點是否可以使得i号頂點到j号頂點之間的路程變得更短。即判斷e[i][2] e[2][j]是否比e[i][j]要小，代碼實現為如下↓

在隻允許經過1和2号頂點的情況下，任意兩點之間的最短路程更新為：

通過上圖得知，在相比隻允許通過1号頂點進行中轉的情況下，這裡允許通過1和2号頂點進行中轉，使得e[1][3]和e[4][3]的路程變得更短了。

同理，繼續在隻允許經過1、2和3号頂點進行中轉的情況下，求任意兩點之間的最短路程。任意兩點之間的最短路程更新為：

最後允許通過所有頂點作為中轉（在雙重循環外再嵌套一個循環），任意兩點之間最終的最短路程為：

整個算法過程雖然說起來很麻煩，但是代碼實現卻非常簡單，核心代碼就是一個三重循環：

這段代碼的基本思想就是：最開始隻允許經過1号頂點進行中轉，接下來隻允許經過1和2号頂點進行中轉……允許經過1~n号所有頂點進行中轉，求任意兩點之間的最短路程。用一句話概括就是：從i号頂點到j号頂點隻經過前k号點的最短路程。其實這是一種“動态規劃”的思想。

Floyd算法可以求出任意兩個點之間最短路徑。它的時間複雜度是O(n³)，空間複雜度是O(n²)。令人很震撼的是它竟然隻有五行代碼，實現起來非常容易。

Floyd算法适用于APSP(All Pairs Shortest Paths，多源最短路徑)，是一種動态規劃算法，稠密圖效果最佳，邊權可正可負。此算法簡單有效，由于三重循環結構緊湊，對于稠密圖，效率要高于執行V(V為頂點數)次Dijkstra算法，也要高于執行V次SPFA算法。

優點：容易理解，可以算出任意兩個節點之間的最短距離，代碼編寫簡單。

缺點：時間複雜度比較高，不适合計算大量數據。

如果需要求出各點之間最短路徑所經過的節點，隻需增加一個前驅數組即可。如p[i][j]，當點p[i][j]經過k點能取得更短路徑時，令

p[i][j]=p[k][j]; // 更改j的前驅為k

如點4至點3的最短距離為：10，路線:4 1 2 3，是怎樣求出來的呢？程序運行完後，由數組p[i][j]即可得出此路徑（參照最後源代碼和最後運行結果）：

p[4][3]＝2 p[4][2]＝1 p[4][1]＝4 // i=p[i][j]時結束路徑搜索

因為是按順序求出的前驅，所以颠倒一下順序（使用棧）即可。

Floyd算法由Robert W. Floyd（羅伯特·弗洛伊德）于1962年發表在“Communications of the ACM”上。同年Stephen Warshall（史蒂芬·沃舍爾）也獨立發表了這個算法。所以該算法也稱為Floyd-Warshall算法。Robert W．Floyd這個牛人是朵奇葩，他原本在芝加哥大學讀的文學，但是因為當時美國經濟不太景氣，找工作比較困難，無奈之下到西屋電氣公司當了一名計算機操作員，在IBM650機房值夜班，并由此開始了他的計算機生涯。此外他還和J.W.J. Williams（威廉姆斯）于1964年共同發明了著名的堆排序算法HEAPSORT(堆排序算法)。Robert W．Floyd在1978年獲得了圖靈獎。

Robert W.Floyd(1936-2001)↓

Stephen Warshall (1935–2006)↓

迪傑斯特拉dijkstra算法是一個單源最短路徑的算法，即隻能求得一個頂點到其它各頂點之間的最短路徑。如果我們每次以一個頂點為源點，重複執行dijkstra算法n次，這樣便可以求得每一頂點之間的最短路徑。關于dijkstra算法，詳細内容可由下面鍊接去了解。

迪傑斯特拉dijkstra算法：一個既貪心又最優的圖的最短路徑算法

另外需要注意的是，Floyd算法不能解決帶有“負權回路”（或者叫“負權環”）的圖，因為帶有“負權回路”的圖沒有最短路。例如下面這個圖就不存在1号頂點到3号頂點的最短路徑。因為1→2→3→1→2→3→…→1→2→3這樣路徑中，每繞一次1→2→3這樣的環，最短路就會減少1，永遠找不到最短路。實際情況是，如果一個圖中帶有“負權回路”，那麼這個圖則沒有最短路。

附源代碼：

#include <stdio.h> #include <stdlib.h> #include <stack> using namespace std; #define N 10 #define inf 99999999 int e[N][N]; // 頂點數組 int p[N][N]; // 前驅數組 void output2Darr(int arr[N][N],int n) { for(int i=1;i<=n;i ) { for(int j=1;j<=n;j ) { printf("d",arr[i][j]); } printf("\n"); } } void outputRoute(int i,int j) { stack<int> st; printf("點%d至點%d的最短距離為：%d，路線:",i,j,e[i][j]); st.push(j); while(p[i][j]!=i) { st.push(p[i][j]); j=p[i][j]; } st.push(i); do{ printf("%d ",st.top()); st.pop(); }while(!st.empty()); printf("\n"); } int main() { int k,i,j,n,m,a,b,s; printf("讀入頂點個數n，邊的條數m:\n"); scanf("%d %d",&n,&m); //初始化 for(i=1;i<=n;i ) for(j=1;j<=n;j ) if(i==j) e[i][j]=0; else e[i][j]=inf; printf("讀入邊,頂點a的編号 頂點b的編号 兩個頂點的距離s,如1 2 2;\n"); for(i=1;i<=m;i ) { scanf("%d %d %d",&a,&b,&s); e[a][b]=s; } for(i=1;i<=n;i ) for(j=1;j<=n;j ) if(e[i][j]>0&&e[i][j]<inf) p[i][j]=i; else p[i][j]=-1; printf("初始矩陣e為：\n"); output2Darr(e,n); //Floyd-Warshall算法核心語句 for(k=1;k<=n;k ) // 插點，k for(i=1;i<=n;i ) for(j=1;j<=n;j ) if(e[i][j]>e[i][k] e[k][j] ) { e[i][j]=e[i][k] e[k][j]; p[i][j]=p[k][j]; // 更改j的前驅為k } printf("全部頂點之間的最短路徑為:\n"); output2Darr(e,n); printf("各點的前驅為:\n"); output2Darr(p,n); outputRoute(4,3); outputRoute(3,2); system("pause"); return 0; } /*輸入（可複制） 4 8 1 2 2 1 3 6 1 4 4 2 3 3 3 1 7 3 4 1 4 1 5 4 3 12 */ /*輸出 讀入頂點個數n，邊的條數m: 4 8 讀入邊,頂點a的編号 頂點b的編号 兩個頂點的距離s,如1 2 2; 1 2 2 1 3 6 1 4 4 2 3 3 3 1 7 3 4 1 4 1 5 4 3 12 初始矩陣e為： 0 2 6 4 99999999 0 3 99999999 7 99999999 0 1 5 99999999 12 0 全部頂點之間的最短路徑為: 0 2 5 4 9 0 3 4 6 8 0 1 5 7 10 0 各點的前驅為: -1 1 2 1 4 -1 2 3 4 1 -1 3 4 1 2 -1 點4至點3的最短距離為：10，路線:4 1 2 3 點3至點2的最短距離為：8，路線:3 4 1 2 */

,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部