迪克斯特拉(迪杰斯特拉-Dijkstra)算法--荷兰计算机科学家迪克斯特拉提出。从一个顶点到其他各个顶点的最短路径算法。

每次遍历从起点开始到未访问过的顶点的最短距离

字母表示顶点

字母中间的线段，表示两个顶点联通，所以如图所示，A点和C点未联通,不能从A点直接到达C点.

数字表示两个联通的点之间的距离，点B和点F之间的6，表示两点的距离是6.所以从点A到点C，可以是点A-->B-->C,距离是5，也可以是A-->D-->C，距离是10.

下面想要求出从点A开始到各个点之间的最短的距离.

设计一维数组dis，用来存放点A到各个点的最短距离。

设计一维数组flag，用来存放某点是否已经取得最优路径。flase表示没有取得最优路径。

设计一维数组pre，用来存放访问某点之前，先访问那点

设计mat二维数组，用来存放各相邻点之间的距离.

1000表示两点没有相连，或者是点自己本身.

代码：

package com.wanmait.demo;

import java.util.Arrays;

public class Demo {
	private char point[] = {'A','B','C','D','E','F'};
	private int dis[] = new int[point.length];//A到个顶点的最短距离
	//dis[2]存放A点到C的最短距离
	private boolean flag[] = new boolean[point.length];
	//标记各点距离是否最优   如果flag[3]的值为true  表示A到D的距离已经是最优
	private char pre[] = new char[point.length];
	//对应的访问各点之前 先访问的点  例如pre[2]为D  表示访问C之前先访问D
	private int[][] mat = new int[point.length][point.length];
	//相邻点之间的距离
	
	//start起始点的下标  找point[start]点到各点的最优距离
	public void search(int start)
	{
	
		Arrays.fill(dis, 1000);//默认最优距离都是1000
		dis[start] = 0;//起始点到起始点自己的最优距离是0
		
		this.update(start);
		//更新起点到各个直接到达的点的距离
		
		//除了起始点之外  其他的各点的最优距离
		for (int i = 0; i < point.length-1; i++) 
		{
			//从没有确定最优距离的点中间 找最小距离和点下标
			int minIndex = -1;
			int minDis = 1000;
			for(int j=0;j<point.length;j++)
			{
				if(flag[j]==false&&dis[j]<minDis)
				{
					minIndex = j;
					minDis = dis[j];
				}
			}
			
			//更新最小距离的点到其他各点的距离
			this.update(minIndex);
		}
	}
	
	//更新某个点  到其他各点之间的最短距离
	//index下标对应的点到各点之间的距离
	public void update(int index)
	{
		flag[index] = true;//标记index下标对应的点，已经访问过
		for(int i=0;i<point.length;i++)
		{
			if(flag[i]==false)//下标i对应的点还没有最优路径
			{
				int length = dis[index]+mat[index][i];
				if(length<dis[i])//通过index对应的点到i对应的点的距离笔保存的距离要短
				{
					dis[i] = length;//保存最优距离
					pre[i] = point[index];//保存访问i对应的点之前  先访问index对应的点
				}
			}
		}
	}
	
	//设置相邻点的距离   1000表示相邻点不能联通
	public void init()
	{
		mat[0] = new int[]{1000,3,1000,7,2,1000};
		mat[1] = new int[]{3,1000,2,1000,1000,6};
		mat[2] = new int[]{1000,2,1000,3,1000,1000};
		mat[3] = new int[]{7,1000,3,1000,4,1000};
		mat[4] = new int[]{2,1000,1000,4,1000,5};
		mat[5] = new int[]{1000,6,1000,1000,5,1000};
	}
}

package com.wanmait.demo;

public class Test {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Demo demo = new Demo();
		demo.init();
		demo.search(0);
	}

}