圖說演算法使用JavaScript(三十七)

10-5-2 Folyd演算法

由於Dijkstra的方法只能求出某一點到其他頂點的最短距離，如果要求圖形中任意兩點甚至所有頂點間最短距離，就必須使用Floyd演算法。

Folyd演算法定義：

這樣看起來似乎覺得Floyd演算法相當複雜難懂，我們將直接以實例說明它的演算法則。例如試以Floyd演算法求得各頂點間的最短路徑：

完成：所有頂點間的最短路徑為矩陣A3所示。

由上例可知，一個加權圖形若有n個頂點，則此方法必須執行n次迴圈，逐一產生A1,A2,A3,……….Ak個矩陣。但因Folyd演算法較為複雜，讀者也可以用上一小節所討論的Dijlstra演算法，依序以各頂點為起始頂點，如此一來可以得到相同結果。

JS                 floyd.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');

範例程式有問題！
上半部是跟書一樣，下半部跟書不一樣