迪杰斯特拉算法（Dijkstra）

迪杰斯特拉算法（Dijkstra）

这是一个按路径长度递增的次序产生最短路径的算法。下面我们分为概念讲解和代码实现两大板块。

1.概念理解

多说无意，我们用图来解释吧。比如说下面这张图：绿色代表未走，亮蓝色代表经过这个结点，加粗的边是我们经过的边。

比如要从 V0 到顶点 V1 的最短距离，没有比这更简单了，路径就是 V0 到 V1。

 由于 V1 还与 V2、V3、V4相连，所以可以求出：V0 ---> V1 ---> V2 = 1+3 = 4, V0 ---> V1 ---> V3 = 1+7 = 8, V0 ---> V1 ---> V4 = 1+5 = 6.先在问 V0 到 V2 的最短距离，那答案就是4.如图

 我们要研究 V0 到 V3 的最短路径，可以看出有 V1 , V4 这两个结点路径。先求出 V0 到 V4 的最短路径。求 V4 时，和它相邻的是 V1 ,V2 那么只需要在V1 的最短路径（我们已经求了是1）加上5和 V2 的最短路径（我们已经求了是4）加上 1 来最比较即可获取 V4 的最短路径。V0 ---> V1 --->V4 = 1 +5 = 6 ,V0 ---> V1 ---> V2 ---> V4 = 4+1 = 5。可知 V0到V4的最短路径是5。再去求 V0 到 V3. V0 ---> V1 ---> V3 = 1+7 = 8, V0 ---> V1 ---> V2 ---> V4 ---> V3 = 5+2 =7.所以V0 到 V3的最短路径是7.

 

总结：求V0到Vn的最短路径，由结果往前推，依次求他们相邻的最短路径，然后加上权值求出这两点的最短路径。

2.代码实现

package datastructure.graph;
import java.util.Arrays;
import matrix.IntMatrix;
	 
public class Net {
	public static final int MAX_DISTANCE = 10000;
	
	//结点数目
	int numNodes;
	
	// 权重矩阵，为了简单起见，我们用int表示权重
	IntMatrix weightMatrix;
	
	// 第一个构造方法
	public Net(int paraNumNodes) {
		numNodes = paraNumNodes;
		weightMatrix = new IntMatrix(numNodes, numNodes);
		for (int i = 0; i < numNodes; i++) {
			
			Arrays.fill(weightMatrix.getData()[i], MAX_DISTANCE);
		} // Of for i
	} // Of the first constructor
	
	// 第二个构造方法
	public Net(int[][] paraMatrix) {
		weightMatrix = new IntMatrix(paraMatrix);
		numNodes = weightMatrix.getRows();
	} // Of the second constructor
	
	public String toString() {
		String resultString = "This is weight matrix of graph.rn" + weightMatrix;
		return resultString;
	}
	
	// Dijstra
	public int[] dijkstra(int paraSource) {
		// 第一步初始化
		int[] tempDistanceArray = new int[numNodes];
		for (int i = 0; i < numNodes; i++) {
			tempDistanceArray[i] = weightMatrix.getValue(paraSource, i);
		} // Of for i
		int[] tempParentArray = new int[numNodes];
		Arrays.fill(tempParentArray, paraSource);
		// -1 没有父亲
		tempParentArray[paraSource] = -1;
		
		// 访问将不在考虑
		boolean[] tempVistedArray = new boolean[numNodes];
		tempVistedArray[paraSource] = true;
		
		// 第二步，主要回路
		int tempMinDistance;
		int tempBestNode = -1;
		for (int i = 0; i < numNodes - 1 ; i++) {
			// 2.1 找出最合适的结点
			tempMinDistance = Integer.MAX_VALUE;
			for (int j = 0; j < numNodes; j++) {
				// 这个结点被访问
				if(tempVistedArray[j]) {
					continue;
				} // Of if
				
				if(tempMinDistance > tempDistanceArray[j]) {
					tempMinDistance = tempDistanceArray[j];
					tempBestNode = j;
				} // Of if
			} // Of for j
			
			tempVistedArray[tempBestNode] = true;
			
			// 2.2 准备下一个轮
			for(int j = 0; j= MAX_DISTANCE) {
					continue;
				} // Of if
				
				if(tempDistanceArray[j] > tempDistanceArray[tempBestNode] + weightMatrix.getValue(tempBestNode, j)) {
					// 改变路径
					tempDistanceArray[j] = tempDistanceArray[tempBestNode] + weightMatrix.getValue(tempBestNode, j);
					// 改变父亲
					tempParentArray[j] = tempBestNode;
				} // Of if
			} // Of for j
			
			// 测试
			System.out.println("The distance to each node: "+ Arrays.toString(tempDistanceArray));
			System.out.println("The parent to each node: "+ Arrays.toString(tempParentArray));
		} // Of for i
		
		// 第三步 用于调试的输出
		System.out.println("Finally");
		System.out.println("The distance to each node: " + Arrays.toString(tempDistanceArray));
		System.out.println("The parent of each node: " + Arrays.toString(tempParentArray));
		return tempDistanceArray;
	} // Of dijkstra
}