迪杰斯特拉算法(Dijkstra)-Java实现

迪杰斯特拉算法也是求两点之间最短路径的算法，它的思想和普利姆算法有点相似，不断通过已找到点集合和未找到点之间的集合之间的最短路径。

这个算法需要用到三个数组，一个是存储结点是否已经访问，一个是结点到起始点的最短距离，还有一个是结点到起始点第一个需要经过的点。我们不断通过迭代更新这三个数组，最终就可以得到每个点到起始点的最短距离数组了。

接下来可以结合代码理解,我也把代码注释写的尽量详细。

//是否已经访问过
private boolean[] isVisited;
//第一个经过的结点
private int[] pre;
//到起始点的最短距离
private int[] dis;
//图的矩阵
private int[][] edges;
//点的数量
private int vertexs;

//param: 起始点的索引
public void dijkstra(int index) {
	//把起始点设置为已经访问
	isVisited[index] = true;
	//更新当前点相邻的点到起始点的距离
	update(index);
	//每次一条边n-1条
	for(int i = 1; i < vertexs; i++ ) {
		//获取最小的边并返回这个点的索引
		int j = updateRoot();
		//更新当前点相邻的点到起始点的距离
		update(j);
	}
}

//根据索引更新与这个点相邻边的距离
public void update(int index) {
	for(int i = 0; i < vertexs; i++) {
		//当前结点到目标结点+当前结点到起始点的距离
		int len = dis[index] + edges[index][i];
		if（len < dis[i] && !isVisited）{
			//更新这个点到已遍历结点的最短一条路径
			dis[i] = len;
			//更新这个点的父节点
			pre[i] = index;
			
		}
	}
}

//选出最短的一条边，并把这个点加入集合
public void updateRoot() {
	min = 10000;
	index = 0
	for(int i = 0; i < vertexs; i++) {
		//如果这条边最短且这个点没有被访问
		if(dis[i] < min && !isVisited[i]) {
			min = dis[i];
			index = i;
		}
	}
	//循环完成，改变这个点的标志
	isVisited[index] = true;
}

迪杰斯特拉到此就算完成了，可能我文字功底还是太弱，总是不能完全的解释它，大家可以上B站查看动图。