单源最短路径（Dijkstra算法）

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法（单源最短路径），解决的是有权图中最短路径问题，采用贪心的策略。
如下图：求顶点1到顶点5的最短路径长度是多少.

核心思路：从源点到终点的最短路径所经过的节点也一定是从源点到此节点的最短路径！
需要一个dist数组记录从源点到各个节点的最短路径长度
需要一个map二维数组记录了图的权值信息
需要一个visit数组记录节点当前到源的距离是否是最短的了，若最短了，则不再变动，对应着dist相应节点也不再变动

/**
 * 单源最短路径问题（贪心）
 * @author 煨酒小童
 *
 */
public class Dijkstra {
	static int max=9999;
	public static void main(String[] args) {
		int n=5;
		int map[][]=new int[n+1][n+1];
		for(int i=0;i<=n;i++)
			for(int j=0;j<=n;j++)
				map[i][j]=max;
		map[1][2]=10;map[1][5]=100;map[1][4]=30;
		map[2][3]=50;map[3][5]=10;map[4][3]=20;map[4][5]=60;
		int v=1;
		int dist[]=new int[n+1];
		int prev[]=new int[n+1]; //记录的是源到顶点i上最短路径上的前一个顶点
		Dijkstra1(v,map,dist,prev);
		for(int i=1;i<=n;i++)
			System.out.println(dist[i]+" ");//dist[5]就是问题的解
		
	}
    //源点，邻接矩阵，存储答案的数组，路径存储
	private static void Dijkstra1(int v, int[][] map, int[] dist, int[] prev) {
		int n=dist.length-1;
		boolean visit[]=new boolean[n+1];
		for(int i=1;i<=n;i++) {
			dist[i]=map[v][i];//源点到各个节点的距离
			visit[i]=false;
			if(map[v][i]<max) prev[i]=0;  //不存在(都没有路径嘛)
			else prev[i]=v;

		}
		visit[v]=true;dist[v]=0;
		//每一次循环都可以创造一个最短路径
		for(int i=1;i<=n;i++) {
			int temp=max;	//从源到index中的最小和的值
			int index=0;	//dist中最小的那个节点
			//这里找出dist中的最小值,并记录是哪个节点
			for(int j=1;j<=n;j++) {
				if(!visit[j] && temp>dist[j]) {
					temp=dist[j];
					index=j;
				}
			}
			visit[index]=true;
			 //从最短路径那里再往外衍生更新dist中的最短路径
			for(int j=1;j<=n;j++) {
				if(!visit[j] && map[index][j]<max) {
					int newdist=temp+map[index][j];
					if(newdist<dist[j]) {
						dist[j]=newdist;
						prev[j]=index;  //与dist数组一样，这个是动态修改的，只会在最后一步确定结果
					}
				}
			}
		}
		
	}

}

算法迭代过程

参考视频