学步园

单源最短路径问题（Dijkstra算法）的java实现（贪心算法）

具体问题描述以及C/C++实现参见网址

http://blog.csdn.net/liufeng_king/article/details/8726066

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
*/