/*
 * 设置一个Ｕ集合，包含最小路径长度和上一个结点
 * Ｖ－Ｕ集合表示还没有进行调整
 * 把Ｖ－Ｕ集合逐渐加入U中，并调整最小路径
 * */

public class Dijkstra {
	
	private static int MAX = 10000;
	
	public static void dijkstra(GraphMatrix grap, Path dist[]){
//		初始化V0
		init(grap,dist);
		
		int n = dist.length;
		int minw = MAX;
		int mv = 0;
		
		for(int i=1;i<n;i++){
			int j;
			for(j=1;j<n;j++){
				if(grap.arcs[j][j]==0 && dist[j].length<MAX){
					mv=j;
					minw = dist[j].length;
					grap.arcs[mv][mv]=1;  
				}
			}
			
			if(mv == 0) break;
			
			for(j=1;j<n;j++){
				if(grap.arcs[j][j]==0 && dist[j].length > dist[mv].length + grap.arcs[mv][j]){
					dist[j].length = dist[mv].length + grap.arcs[mv][j];
					dist[j].pre = mv;
				}
			}
			
			
		}
		
	}
	
	
	
//	初始化，把V0放入U中，矩阵对角线为1表示在U中
	private static void init(GraphMatrix grap, Path[] dist) {
		// TODO Auto-generated method stub
		for(int i=0;i<dist.length;i++){
			grap.arcs[0][0] = 1; //表示v0进入U集合中
			dist[i].length = grap.arcs[0][i];
			if(grap.arcs[0][i]!=MAX){
				dist[i].pre = 0;
			}else{
				dist[i].pre = -1;
			}
		}
	}
	
	
}


class GraphMatrix{
	int[] vrcs;
	int[][] arcs;
}

class Path{
	int length;
	int pre;
}