js图的数据结构处理---弗洛伊德算法

		function Graph() {
			this.graph = [
				[0, 2, 4, 0, 0, 0],
				[0, 0, 1, 4, 2, 0],
				[0, 0, 0, 0, 3, 0],
				[0, 0, 0, 0, 0, 2],
				[0, 0, 0, 3, 0, 2],
				[0, 0, 0, 0, 0, 0]
			];
			var vertices = ["A","B","C","D","E","F"];
			//弗洛伊德算法
			this.floydWarshall = function(){
				var dist = [],
				prev = [],
				length = this.graph.length,
				i,j,k;
				
				for(var i = 0 ; i < length; i++){
					dist[i] = [];
				
					for(var j = 0; j < length; j++){
						dist[i][j] = this.graph[i][j];
						if( dist[i][j] == 0 && i !== j){
							//将不通的路，设置为无穷大
							dist[i][j] = Infinity;
						}
					}
				}
				
				for (k = 0; k < length; k++) {//起点
					prev[k] = {};
					prev[k][vertices[k]] = null;
					for (i = 0; i < length; i++) {//中间点
						for (j = 0; j < length; j++) {//结束点
							if (dist[k][i] + dist[i][j] < dist[k][j]) {
								//dist[k][i] 相通
								//dist[i][j] 也相通
								//dist[k][j] 一定相通
								//Infinity + Infinity == Infinity    ->  true
								dist[k][j] = dist[k][i] + dist[i][j];
								
								prev[k][vertices[j]] = vertices[i]; //记录前溯点
							}
						}
					}
				}
				return {
					dist:dist,
					prev:prev
				};
			}
			
			this.path = function(){
				var predecessorsArr = this.floydWarshall()['prev'];
				
				for(var i = 0; i < predecessorsArr.length; i++){
					console.log(getPath(predecessorsArr[i]));	
				}
				
			}
			
			function getPath(predecessors){
			
				var paths = [];
				for(var i = 0; i < vertices.length; i++){
					var toVertex = vertices[i], 
					path = []; 
					while(toVertex){
						path.push(toVertex);
						toVertex = predecessors[toVertex];
					}
					
					var s = path.join('-');
					paths.push(s);
				}
				return paths;
			}
		}
		
		var graph = new Graph();
		console.log(graph.floydWarshall());
		graph.path();
		//弗洛伊德算法
		//1、把dist数组初始化为每个顶点之间的权值，因为i到j可能的最短距离就是这些顶点间的权值
		//2、例如当： k为A，i为B，j为D，则判断 AB + BD < AD,这里有点像向量，实际上就是找路径的中间点，如果更小，就赋值
		//3、其中，为了求AD的最小距离，就不断找 AD之间的其他点，相加的最小距离
		

		//对图中每一个顶点执行Dijkstra（迪杰斯特拉）算法，也可以得到相同的结果