在數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)當(dāng)中，圖的處理是必不可少的一項(xiàng)佛纫，對圖進(jìn)行處理時缝彬，最短路徑的求取具有較強(qiáng)的使用性和可行性萌焰，在此，我簡單地對求取最短路徑的算法之一——弗洛伊德算法做出簡單的講解谷浅。
弗洛伊德算法在實(shí)現(xiàn)的時候一個重要的特點(diǎn)就是用循環(huán)的嵌套來進(jìn)行逐個的判斷和更新扒俯。此算法區(qū)分于迪杰斯特拉算法的很大的優(yōu)點(diǎn)就是弗洛伊德算法可以在實(shí)現(xiàn)過后實(shí)現(xiàn)了圖中每一個結(jié)點(diǎn)的對其余各個結(jié)點(diǎn)的最短路徑，而后者只是針對一個目標(biāo)結(jié)點(diǎn)計算出該結(jié)點(diǎn)到其他結(jié)點(diǎn)的最短路徑一疯。但是撼玄，由于這次只是做弗洛伊德算法的講解，對于迪杰斯特拉算法便不予贅述墩邀。
如果要求任意兩個結(jié)點(diǎn)之間的最短路徑掌猛，我們可能已經(jīng)有了簡單的想法，在兩個結(jié)點(diǎn)之間存在直接的路徑時眉睹，比較這個路徑和經(jīng)過一次結(jié)點(diǎn)的中轉(zhuǎn)荔茬，甚至二次只盹、三次、以及多次的中轉(zhuǎn)之后的權(quán)值之和比較兔院，最短的權(quán)值之和就可以確定該路徑為最短路徑；若兩者沒有直接路徑站削，則需考慮在經(jīng)過結(jié)點(diǎn)的中轉(zhuǎn)以后坊萝，無論經(jīng)過了幾次中轉(zhuǎn)結(jié)點(diǎn)，只要選出權(quán)值最短的路徑许起，該路徑就是最短路徑十偶。
這便是最短路徑的求取方法。
這個過程看似實(shí)現(xiàn)較難园细，但加上了一些輔助變量后惦积，便可以順利實(shí)現(xiàn)。
但是要加入哪些輔助變量呢猛频？首先需要考慮到的是path數(shù)組存放計算出的最短路徑的結(jié)果狮崩。行標(biāo)表示起點(diǎn)結(jié)點(diǎn)，列標(biāo)表示終點(diǎn)結(jié)點(diǎn)鹿寻，則該位置存放的數(shù)據(jù)則是終點(diǎn)結(jié)點(diǎn)的前一個結(jié)點(diǎn)睦柴。
例如：從a到達(dá)c的最短路徑為：a—》b—》c；若a的下標(biāo)是1毡熏；c的下標(biāo)是4坦敌；b的下標(biāo)是2；則path[1][4]=2;若從c到e的最短路徑是c—》d—》a—》e痢法；c狱窘，d，a财搁，e的下標(biāo)分別為3,4,1,5蘸炸；
則path[3][5]=1；在查找最短路徑時的順序則是path[3][5]=1,path[3][1]=4;path[3][4]=3妇拯；路徑順序就為：下標(biāo)5《--1《--4《--3幻馁。
另外，需要加入輔助數(shù)組D越锈，該數(shù)組用于記錄兩結(jié)點(diǎn)直接的最短路徑長度如D[0][3]=3仗嗦；表示從0到3的最短路徑長度為3；
現(xiàn)在甘凭，讓我們回到上述自己設(shè)想的問題稀拐，如何比較兩個結(jié)點(diǎn)之間的路徑長度和呢？
在弗洛伊德算法中丹弱，采用的方法是權(quán)值的更新德撬，以下是弗洛伊德的具體算法铲咨，以便于講解
下面開始對代碼展開講解：
個人認(rèn)為，算法的實(shí)現(xiàn)可以分為兩部分蜓洪，其中每一部分可以用以上的兩個for循環(huán)來劃分纤勒，第一個for循環(huán)如下，進(jìn)行的是權(quán)值和路徑的初始化
D[i][j]=G.arc[i][j]; ? ? ? ? ?//將下標(biāo)為i的結(jié)點(diǎn)與相關(guān)的結(jié)點(diǎn)權(quán)值初始化隆檀，如果有直接路徑摇天，則長度是已知權(quán)值，否則的初始化結(jié)果是無窮
if (D[i][j]<Maxint)
p[i][j]=i; ? ? ? ? ? ? ? ? ? ? ? //已初始化后恐仑，有直接路徑的話終點(diǎn)結(jié)點(diǎn)的前一個結(jié)點(diǎn)便是起點(diǎn)結(jié)點(diǎn)
else
p[i][j]=0; ? ? ? ? ? ? ? ? ? ? ?//沒有直接路徑泉坐，進(jìn)行特殊標(biāo)記。
進(jìn)行了初始化之后裳仆，數(shù)組D內(nèi)的元素應(yīng)該與圖D的權(quán)值數(shù)組G.arc相等腕让，并且數(shù)組path內(nèi)的數(shù)據(jù)也根據(jù)圖中結(jié)點(diǎn)間的關(guān)系獲得了初值。
第二部分體現(xiàn)為針對兩個目標(biāo)結(jié)點(diǎn)加入圖中的每一個結(jié)點(diǎn)作為中轉(zhuǎn)結(jié)點(diǎn)進(jìn)行路徑長度的判斷歧斟，根據(jù)判斷結(jié)果更新兩個數(shù)組內(nèi)容纯丸，這個算法很容易使人聯(lián)想到密碼破解時使用的窮舉法。
代碼如下：
for (i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++) ? ? ?//起始結(jié)點(diǎn)
for(k=0;k<G.vexnum;k++) ? ?//終點(diǎn)結(jié)點(diǎn)
if (D[j][k]>D[j][i]+D[i][k]) ? ? //j构捡，k是需要更新的兩個結(jié)點(diǎn)液南，現(xiàn)在欲在這兩個結(jié)點(diǎn)中加入下標(biāo)為i的結(jié)點(diǎn)，并判斷加入新的結(jié)點(diǎn)以后的路徑長度勾徽。
{
D[j][k]=D[j][i]+D[i][k];
p[j][k]=p[k][i]; ? ? ? ? ? ? ? ? ? //可以更新滑凉，則進(jìn)行數(shù)據(jù)更新。
}
到此喘帚，循環(huán)結(jié)束畅姊，最短路徑的查找也完成。
需要說明的是吹由，每一次數(shù)據(jù)的更新若未，path數(shù)組都保存有前一個結(jié)點(diǎn)的信息，如圖：
首先path[0][1]=0;D[0][1]=6;之后倾鲫，有初始化后的結(jié)果：path[0][2]=0,D[0][2]=1,2和1之間沒有路徑故D[2][1]=Maxint,path[0][1],D[0][1]無需更新粗合，之后，判斷0和3,D[0][3]=Maxint是初始化的結(jié)果乌昔，更新加入2之后成了path[0][3]=2;D[0][3]=3;path[2][3]=0,D[2][3]=2隙疚，path[3][1],D[3][1]=1加入任意結(jié)點(diǎn)之后無需更新，故保持磕道；再進(jìn)行path[0][1],D[0][1]的判斷時供屉，嘗試加入結(jié)點(diǎn)2，不成功，再嘗試加入點(diǎn)3時伶丐，由于D[0][3]已經(jīng)更新為3悼做，所以滿足更新條件，D[0][1]=4,path[0][1]=3完成了從0到1中間大于1個中轉(zhuǎn)結(jié)點(diǎn)的實(shí)現(xiàn)哗魂。
總結(jié)在于肛走，第二部分使用三個for語句的嵌套起到了重要的作用，數(shù)據(jù)的更新和信息的保存也需要準(zhǔn)確理解录别。
