愛華網(wǎng)算法基本思想
假設(shè)求頂點(diǎn)Vi到Vj的最短路徑。弗洛伊德算法依次找從Vi到Vj，中間經(jīng)過結(jié)點(diǎn)序號(hào)不大于0的最短路徑，不大于1的最短路徑，…直到中間頂點(diǎn)序號(hào)不大于n-1的最短路徑，從中選取最小值，即為Vi到Vj的最短路徑。
算法具體描述
若從Vi到Vj有弧，則從Vi到Vj存在一條長度為弧上權(quán)值（arcs[i][j]）的路徑，該路徑不一定是最短路徑，尚需進(jìn)行n次試探。
首先考慮從Vi到Vj經(jīng)過中間頂點(diǎn)V0的路徑（Vi，V0，Vj）是否存在，也就是判斷?。╒i，V0）和（V0，Vj）是否存在。若存在，則比較（Vi，Vj）和（Vi，V0，Vj）的路徑長度取較短的為從Vi到Vj的中間頂點(diǎn)序號(hào)不大于0的最短路徑。
在此路徑上再增加一個(gè)頂點(diǎn)V1，也就是說，如果（Vi，…V1）和（V1，…Vj）分別是當(dāng)前找到的中間頂點(diǎn)序號(hào)不大于0的最短路徑，那么，（Vi，…V1，…Vj）就有可能是從Vi到Vj的中間頂點(diǎn)序號(hào)不大于1的最短路徑。將它和已經(jīng)得到的從Vi到Vj中間頂點(diǎn)序號(hào)不大于0的最短路徑相比較，從中選出最短的作為從Vi到Vj中間頂點(diǎn)序號(hào)不大于1的最短路徑。
然后，再增加一個(gè)頂點(diǎn)V2繼續(xù)進(jìn)行這個(gè)試探過程。
一般情況下，若（Vi，…Vk）和（Vk，…Vj）分別是從Vi到Vk和從Vk到Vj的中間頂點(diǎn)序號(hào)不大于k-1的最短路徑，則將（Vi，…，Vk，…Vj）和已經(jīng)得到的從Vi到Vj的中間頂點(diǎn)序號(hào)不大于k-1的最短路徑相比較，其長度最短者即為從Vi到Vj的中間頂點(diǎn)序號(hào)不大于k的最短路徑。
經(jīng)過n次比較之后，最后求得的便是從Vi到Vj的最短路徑。
按此方法可同時(shí)求得各對(duì)頂點(diǎn)之間的最短路徑。
現(xiàn)定義一個(gè)n階方陣序列
D（-1），D（0），D（1），…，D（k），…，D（n-1）
其中
D（-1）[i][j]=arcs[i][j]
D（k）[i][j]=Min{D（k-1）[i][j],D（k-1）[i][k]+D（k-1）[k][j]}0≤k≤n-1
上述公式中，D（1）[i][j]是從Vi到Vj的中間頂點(diǎn)序號(hào)不大于k的最短路徑長度；D（n-1）[i][j]是從Vi到Vj的最短路徑長度。
算法實(shí)現(xiàn)
void shortestpath_Floyd(MgraphG,pathmatrix &P[],Distancmatrix &D){//用Floyd算法求有向網(wǎng)G中各對(duì)頂點(diǎn)v和w之間的最短路徑P[v][w]及其帶權(quán)路徑長度D[v][w]。
//若P[v][w][u]為TRUE，則u是從v到w當(dāng)前求得最短路徑上的頂點(diǎn)。
For(v=0;v<G.vexnum;++v)//各對(duì)頂點(diǎn)之間路徑和距離初始化
For(w=0;w<G.vexnum;++w){
D[v][w]=G.arcs[v][w];
For(u=0;u<G.vexnum;++u)P[v][w][u]=false;
If(D[v][w]<INFINITY){//從v到w有直接路徑
P[v][w][v]=true;P[v][w][w]=true;
}//if
}//for
for (u=0;u<G.vexnum;++u)
for (v=0;v<G.vexnum;++v)
for (w=0;w<G.vexnum;++w)
if(D[v][u]+D[u][w]<D[v][w]){//從v經(jīng)u到w的一條路徑更短
D[v][w]= D[v][u]+D[u][w]；
For (I=0;I<G.vexnum;++I)
P[v][w][I]=P[v][u][I]|| P[u][w][I];
}//if
}//shortestpath_Floyd
