10-5-2 Folyd演算法
由於Dijkstra的方法只能求出某一點到其他頂點的最短距離，如果要求圖形中任意兩點甚至所有頂點間最短距離，就必須使用Floyd演算法。
Folyd演算法定義：
這樣看起來似乎覺得Floyd演算法相當複雜難懂，我們將直接以實例說明它的演算法則。例如試以Floyd演算法求得各頂點間的最短路徑：
完成：所有頂點間的最短路徑為矩陣A3所示。
由上例可知，一個加權圖形若有n個頂點，則此方法必須執行n次迴圈，逐一產生A1,A2,A3,……….Ak個矩陣。但因Folyd演算法較為複雜，讀者也可以用上一小節所討論的Dijlstra演算法，依序以各頂點為起始頂點，如此一來可以得到相同結果。
JS
const SIZE=7;
const NUMBER=6;
const INFINITE=99999;
var Graph_Matrix=[[0,0,0,0,0,0,0],
[0,0,0,0,0,0,0],
[0,0,0,0,0,0,0],
[0,0,0,0,0,0,0],
[0,0,0,0,0,0,0],
[0,0,0,0,0,0,0],
[0,0,0,0,0,0,0]];
var distance=[];
for (let i=0; i<SIZE; i++) {
distance[i]=new Array();
for (let j=0; j<SIZE; j++)
distance[i][j]=0;
}
var BuildGraph_Matrix=(Path_Cost)=> {
for (let i=1; i<SIZE; i++) {
for (let j=1; j<SIZE; j++) {
if (i==j)
Graph_Matrix[i][j]=0;
else
Graph_Matrix[i][j]=INFINITE;
}
}
let i=0;
while (i<SIZE) {
Start_Point=Path_Cost[i][0];
End_Point=Path_Cost[i][1];
Graph_Matrix[Start_Point][End_Point]=Path_Cost[i][2];
i+=1;
}
}
var shortestPath=(vertex_total)=> {
for (let i=1; i<vertex_total+1; i++) {
for (let j=1; j<vertex_total+1; j++) {
distance[i][j]=Graph_Matrix[i][j];
distance[j][i]=Graph_Matrix[j][i];
}
}
for (let k=1; k<vertex_total+1; k++) {
for (let i=1; i<vertex_total+1; i++) {
for (let j=1; j<vertex_total+1; j++) {
if (distance[i][k]+distance[k][j]<distance[i][j])
distance[i][j]=distance[i][k]+distance[k][j];
}
}
}
}
Path_Cost=[[1,2,20],[2,3,30],[2,4,25],
[3,5,28],[4,5,32],[4,6,95],[5,6,67]];
BuildGraph_Matrix(Path_Cost);
process.stdout.write('========================================\n');
process.stdout.write(' 所有頂點兩兩之間的最短距離： \n');
process.stdout.write('========================================\n');
shortestPath(NUMBER);
process.stdout.write('\t頂點1\t頂點2\t頂點3\t頂點4\t頂點5\t頂點6\n');
for (let i=1; i<NUMBER+1; i++) {
process.stdout.write('頂點'+i+'\t');
for (let j=1; j<NUMBER+1; j++) {
process.stdout.write(distance[i][j]+'\t');
}
process.stdout.write('\n');
}
process.stdout.write('=========================================\n');範例程式有問題！
