shortestpath.java

本程序实现了单源最短路径

//本程序实现单源最短路径
//陈勇 06计算机1班  0611701011
//敬请老师指正
import java.io.*;
import java.util.*;
public class ShortestPath{
     public static void main(String[] args){
         int n=5;
         float[][] a=new float[n+1][n+1];
         //数组初始化
         for(int i=0;i<=5;i++)
           for(int j=0;j<=5;j++)
             a[i][j]=Float.MAX_VALUE;
         a[1][2]=10;
         a[1][4]=30;
         a[1][5]=100;
         a[2][3]=50;
         a[3][5]=10;
         a[4][3]=20;
         a[4][5]=60;

         float[] dist=new float[n+1];//保存最短距离
         int[] prev=new int[n+1];//保存路径
         
         dijkstra(1,a,dist,prev);//调用Dijkstra算法
         
         System.out.println("The ShortestPath From 1 to 5 is:");
         print(prev,1,5);	//打印输出

		 }
	public static void print(int[] prev,int s,int d)//利用递归实现打印最短路径
	{
		if(d==s)
			System.out.print(s+" ");
		else
		{print(prev,s,prev[d]);
		 System.out.print(d+" ");	}
	}	 
	 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]==Float.MAX_VALUE)prev[i]=0;
			 else prev[i]=v;
		 }
		 dist[v]=0;
		 s[v]=true;
		 for(int i=1;i<n;i++)
		 {
			 float temp=Float.MAX_VALUE;
			 int u=v;
			 for(int j=1;j<=n;j++)
			   if((!s[j])&&(dist[j]<temp))
			   {
				   u=j;
				   temp=dist[j];
				}
			  s[u]=true;
			  for(int j=1;j<=n;j++)
			      if((!s[j])&&(a[u][j]<Float.MAX_VALUE))
			      {
					  float newdist=dist[u]+a[u][j];
					  if(newdist<dist[j])
					  {
						  dist[j]=newdist;
						  prev[j]=u;
					   }

				  }
		 }
		 }
		 }