nlogndriver.java

这是一个将Dijkstra算法的时间复杂度从O(n*n) 优化为O(nlogn)的方法

// NLogN Driver program
// CNA, S2, 2008
// v 0.2, 02 July 2008 - Nick Falkner

public class NLogNDriver {

    public static void main(String [] args) {

	// Create a timer to allow us to monitor how long it takes.

	StopWatch timer = new StopWatch();

	// All data is read from a config file. Format of the config file
	// is given in the assignment.

	if (args.length < 1) {
	    System.out.println("No config file given, closing down.");
	    System.exit(0);
	}

	// Create the new objects

	boolean debugging = false;
	DijkstraInterface d1 = new NLogN(debugging);
	System.out.println("N*log(N) Test\n");
	// the Dijkstra object is responsible for sanity checking the 
	// args[0] parameter and should stop the program if there is
	// no file of that name.
	
	d1.initialiseNetwork(args[0]);
	
	// Set the source node
	
	NetworkNode sourceNode = d1.getSourceNode();
	
	// The computation of the shortest path is timed.
	
	timer.start();
	
	// Determine the shortest paths through the network.
	
	d1.computeShortestPaths(sourceNode);
	
	// And collect the timing data.
	
	timer.stop();
	long time = timer.getElapsedTime();
	
	// Finally, display the results and elapsed time.
	    
	System.out.println();
	d1.displayFinalNetwork();
	System.out.println();
	System.out.println("Elapsed time for computation is "+time);
	System.out.println();
	
    }
    

}