迪杰斯特拉算法-某个源点到其余各点的最短路径-java

时间复杂度：O(n^2)

import java.util.Scanner;


public class Main {
	public static void ShortestPast_DIJ(int[][] G,int v0,boolean[][] P,int[] D)
	{
		int v,w;
		boolean[] f=new boolean[G.length];
		
//		printP(P);
		for(v=0;v<G.length;++v)
		{
			f[v]=false; D[v]=G[v0][v];
			for(w=0;w<G.length;++w) P[v][w]=false; //设空路径
			if(D[v]<Integer.MAX_VALUE)
			{
				P[v][v0]=true;
				P[v][v]=true;
			}
		}
//		printP(P);
		D[v0]=0; f[v0]=true;  //初始化，v0顶点属于S集合
		//开始主循环，每次旧的v0到某个顶点v的最短路径，并加v到S集
		for(int i=1;i<G.length;++i) //其余G.length-1个顶点
		{
			int min=Integer.MAX_VALUE;
			for(w=0;w<G.length;++w)
			{
				if(!f[w])		//w顶点在V-S中
					if(D[w]<min)    //w顶点离v0顶点更近
					{
						v=w; min=D[v];
					}
			}
//			System.out.println("#"+v);
			f[v]=true;		//离v0最近的v加入S集
//			System.out.println("old");
//			printP(P);
			for(w=0;w<G.length;++w)   //更新当前最短路径及距离
			{
				if(!f[w]&&(min+G[v][w]<D[w])&&min<Integer.MAX_VALUE&&G[v][w]<Integer.MAX_VALUE)   //修改D[w]和P[w],w属于V-S
				{
					D[w]=min+G[v][w];
					P[w]=P[v].clone(); 
					P[w][w]=true; //P[w]=P[v]+P[w]
				}
			}
//			printP(P);
		}
	}
	public static int[][] readG(Scanner in,int n)
	{
		int[][] G=new int[n][n];
		for(int i=0;i<n;++i)
		{
			for(int j=0;j<n;++j)
			{
				G[i][j]=in.nextInt();
				if(G[i][j]==-1)
					G[i][j]=Integer.MAX_VALUE;
			}
		}
		return G;
	}
	public static void print(int[][] G)
	{
		for(int i=0;i<G.length;i++)
		{
			for(int j=0;j<G.length;++j)
			{
				System.out.print(G[i][j]+" ");
			}
			System.out.println();
		}
	}
	
	public static void printP(boolean[][] P)
	{
		int n=P.length;
		System.out.println();
		for(int i=0;i<n;i++)
		{
			System.out.print(0+":"+i+" ");
			for(int j=0;j<n;j++)
			{
				System.out.print(P[i][j]+" ");
			}
			System.out.println();
		}
	}
	public static void printD(int[] D)
	{
		System.out.println("终点"+"\t最短路径长度");
		for(int i=0;i<D.length;i++)
		{
			if(D[i]<Integer.MAX_VALUE)
				System.out.println(i+"\t"+D[i]);
			else
				System.out.println(i+"\t无");
		}
			
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(System.in);
		int[][] G=readG(in,6);
		int v0=0;
		boolean[][] P=new boolean[6][6];
		int[] D=new int[6];
	
//		print(G);	
		ShortestPast_DIJ(G, v0, P, D);
//		printP(P);
		printD(D);
		
	}
	
}
/*
-1 	-1 	10 	-1 	30 	100
-1 	-1 	5 	-1 	-1 	-1
-1	-1	-1	50	-1	-1
-1	-1	-1	-1	-1	10
-1	-1	-1	20	-1	60
-1	-1	-1	-1	-1	-1 

起点 0
终点	最短路径长度
0	0
1	无
2	10
3	50
4	30
5	60

 */