알고리즘 자바 구현 - 욕심 알고리즘 - 단원 최 단 경로 문제 - Dijkstra 알고리즘

import java.util.Scanner;

public class Dij {
	/**
	 *       
	 * @param v   
	 * @param a         
	 * @param dist                
	 * @param prev       
	 */
	public static void dijkstra(int v,float[][] a,float[] dist,int[] prev){
		
		int n=dist.length-1;
		if(v<1||v>n) return;//     
		boolean[] s=new boolean[n+1];//           
		//   
		for(int i=1;i<=n;i++){
			dist[i]=a[v][i];
			s[i]=false;
			if(dist[i]==-1)
				prev[i]=0;
			else
				prev[i]=v;
		}
		dist[v]=0;//    
		s[v]=true;
		for(int i=1;i<n;i++){//   n-1 
			float temp=Float.MAX_VALUE;
			int u=v;//u          
			for(int j=1;j<=n;j++){//             
				if(!s[j]&&dist[j]<temp&&dist[j]!=-1){
					u=j;
					temp=dist[j];
				}
			}
				s[u]=true;
				for(int j1=1;j1<=n;j1++){//            
					if(!s[j1]&&a[u][j1]!=-1){
						float newdist=dist[u]+a[u][j1];
						if(newdist<dist[j1]||dist[j1]==-1){
							dist[j1]=newdist;
							prev[j1]=u;
						}
					}
				}
		}
		for(int i=2;i<=n;i++){
			System.out.println(i+"        ："+dist[i]+"；    ："+prev[i]);
		}
	}
	public static void main(String[] args) {
		System.out.println("         ：");
		Scanner sc = new Scanner(System.in);
		String line = sc.nextLine();
		int n = Integer.parseInt(line);
		System.out.println("         ：");
		float[][] a = new float[n+1][n+1];//   1  ，    
		float[] dist = new float[n+1]; 
		int[] prev = new int[n+1];
		for(int i=0;i<n;i++){
			line =  sc.nextLine();			
			String[] ds = line.split(",");
			for(int j = 0;j<ds.length;j++){
				a[i+1][j+1]=Float.parseFloat(ds[j]);
			}
		}
		
        //a[][]    1   ，  ，   0        ，     ；-1      
		//float[][] a={{0,0,0,0,0,0},{0,-1,10,-1,30,100},{0,-1,-1,50,-1,-1},{0,-1,-1,-1,-1,10},{0,-1,-1,20,-1,60},{0,-1,-1,-1,-1,-1}};
		//int n=a.length;
		//float[] dist = new float[n];
		//int[] prev = new int[n];
		
		int v =1 ;//   1  
		dijkstra(v,a,dist,prev);
	}
}
/**
 *        
 * 
 *   ：
 5
 -1,10,-1,30,100
-1,-1,50,-1,-1
-1,-1,-1,-1,10
-1,-1,20,-1,60
-1,-1,-1,-1,-1


*   ：
1        ：0.0；    ：0
2        ：10.0；    ：1
3        ：50.0；    ：4
4        ：30.0；    ：1
5        ：60.0；    ：3
*/