cwk2problem2.java

用迪卡斯尔公式求两点之间最短路径,需要一个文本结合 或者网页

import java.io.*;
import java.util.*;

class Cwk2Problem2
{
   public static void main(String args[])
  {

	  try {
		  FileInputStream fstream = new FileInputStream(args[0]);
		  DataInputStream in = new DataInputStream(fstream);
		  BufferedReader br = new BufferedReader(new InputStreamReader(in));
		  String strLine;
		  double AverageOutdegree=0;
		  String u,v,w,first,second,NodeSum,EdgeSum;
		  int u1,v1,w1,NodeSum1 = 0,EdgeSum1 = 0;
		  while ((strLine = br.readLine()) != null)   
		  	{
				char a;
				a = strLine.charAt(0);
				StringTokenizer st = new StringTokenizer(strLine);
				if (a == 'p') 
				{
					first = st.nextToken();
					second = st.nextToken();
					NodeSum = st.nextToken();
					EdgeSum = st.nextToken();
					NodeSum1 = Integer.parseInt(NodeSum);
					EdgeSum1 = Integer.parseInt(EdgeSum);
					AverageOutdegree = EdgeSum1 / NodeSum1;
					break;
				}
			}
		int[][] weight = new int[NodeSum1 + 1][NodeSum1 + 1];
		while ((strLine = br.readLine()) != null)   
		{
			char a;
			a = strLine.charAt(0);
			StringTokenizer st = new StringTokenizer(strLine);
			if( a == 'a')
			{
				first = st.nextToken();
				u = st.nextToken();
				v = st.nextToken();
				w = st.nextToken();
				u1 = Integer.parseInt(u);
				v1 = Integer.parseInt(v);
				w1 = Integer.parseInt(w);
				weight[u1][v1] = w1;
			}
		}
		in.close();
		int SourceNode,FinNode,Min = 0,i,j ,temp,PreviousV,temptarget = 0;
		SourceNode = Integer.parseInt(args[2]);
		FinNode = Integer.parseInt(args[1]);
		PreviousV = SourceNode;
		while(weight[FinNode][SourceNode] != -1)
		{
			Min = -2;
			i = 1;
			while (i <=  NodeSum1) 
			{
				if ( weight[i][SourceNode] != 0 && weight[i][SourceNode] != -1)
				{
					temp = weight[i][SourceNode];
					if (Min == -2)
					{
						Min = temp;
						temptarget = i;
		     			} 
					else {}
					if(Min > temp)
					{
						Min = temp;
						temptarget = i;
					}
				}
				i++ ;
			}
			j = 1;
			while (j <=   NodeSum1) 
			{
				if ( weight[j][temptarget] != 0 && j != temptarget && j != SourceNode && j != PreviousV && weight[j][SourceNode] != -1)
				{
					if (weight[j][SourceNode] > weight[j][temptarget] + weight[temptarget][SourceNode])
					{
						weight[j][SourceNode] = weight[j][temptarget] + weight[temptarget][SourceNode];
						PreviousV = temptarget;
					} 
					if(weight[j][SourceNode] == 0)
					{
						weight[j][SourceNode] = weight[j][temptarget] + weight[temptarget][SourceNode];
					}
				}
				j++;
			}
			weight[temptarget][SourceNode] = -1;
		}	
		System.out.println(Min);
	  }    
catch (Exception e)
	{     
      System.err.println("Error: " + e.getMessage());
	}
  }
}