nlogn.java

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

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

public class NLogN implements DijkstraInterface {
	private boolean debugging;
    private int numOfNodes;
    private int numOfLinks;
    private double infinity = Double.MAX_VALUE;
    private NetworkNode root;
    ArrayList<NetworkNode> nodes = new ArrayList<NetworkNode>();
    PriorityQueue<NetworkNode> copyNodes = new PriorityQueue<NetworkNode>();
    ArrayList<Integer> used = new ArrayList<Integer>();
    ArrayList<NetworkNode> storeN = new ArrayList<NetworkNode>();

    public NLogN(boolean debugging) {
    	
    	this.debugging = debugging;
    	
    }
    
    // This allows the programmer to change the source node for calculation
    // without forcing them to expose their data structure.

    public NetworkNode getSourceNode() {
    	
    	return root;
    	
    }

    // initialiseNetwork opens up and parses the config file, then puts it
    // into the Network storage representation format.
    // Regardless of how you implement this, the network must be ready to 
    // go when we push the 'computeShortestPaths' button.

    public void initialiseNetwork(String filename) {
    	
    	try {
    		
    		// read file 
        	FileReader reader = new FileReader(filename);
        	Scanner readIn = new Scanner(reader);
        	
        	// how many nodes in config file
        	String line = readIn.nextLine();
        	numOfNodes = Integer.parseInt(line);
        	System.out.println("Adding " + numOfNodes + " nodes");
        	
        	for(int i = 0; i < numOfNodes; i++) {
        		
        		if(readIn.hasNextLine()){
        			if(i == 0){
        				// root node's D(v) is 0
        				NetworkNode node = new NetworkNode(readIn.nextLine(),0);
        				nodes.add(node);
        			}else{
        				// other nodes's D(v) initialise to infinity
        				NetworkNode node = new NetworkNode(readIn.nextLine(),infinity);
        			    nodes.add(node);
        			}
        			
        		}
        		
        	}
        	
        	// how many links in config file
        	if(readIn.hasNextLine()){
        		numOfLinks = 2 * Integer.parseInt(readIn.nextLine());
        	}
        	
        	System.out.println("Adding " + numOfLinks + " links");
        	
        	// setting links
        	while(readIn.hasNextLine()) {
        		
        		String thisLine = readIn.nextLine();
        		StringTokenizer linkString = new StringTokenizer(thisLine);
        		String source = linkString.nextToken(" ");
        		String neighbour = linkString.nextToken(" ");
        		double distance = Double.parseDouble(linkString.nextToken(" "));
        		
        		for(int i = 0; i < nodes.size(); i++) {
        			
        			// add links for each node
        			if(source.equals(nodes.get(i).nameOfNode) || neighbour.equals(nodes.get(i).nameOfNode)) {
        				
        				if(debugging){
        					System.out.println("from " + source + " to " + neighbour + " and distance is " + distance);
        					System.out.println("this node is " + nodes.get(i).nameOfNode);
        				}
        					
        				NetworkLink link = new NetworkLink(source,neighbour,distance);
        				nodes.get(i).addLink(link);
        					
        				//System.out.println(nodes.get(i));
        			}
        			
        		}
        		
        		// initialise the linkedList N
        		int pos = 0;
        		used.add(pos);
        		if(source.equals(nodes.get(0).nameOfNode)) {
        			
        			for(int j = 0; j < nodes.size(); j++){
        				
        				if(nodes.get(j).nameOfNode.equals(neighbour)){
        					pos = j;
        				}
        				
        			}
        			
        			used.add(pos);
        			nodes.get(pos).setDistance(distance);
        			nodes.get(pos).setPreviousNode(nodes.get(0));
        			System.out.println("Setting distance to node " + neighbour + " from " + nodes.get(0).nameOfNode + " to " + distance);
        			
        		}else{
        			
        			for(int j = 0; j < nodes.size(); j++){
        				
        				if(nodes.get(j).nameOfNode.equals(neighbour)){
        					pos = j;
        				}
        				
        			}
        			
        			if(!used.contains(pos)){
        				System.out.println("Node " + neighbour + " is currently unreachable from node " + nodes.get(0).nameOfNode);
        			}
        			    
        			used.add(pos);
        			
        		}
        		
        	}
        	// add the source node into the LinkedList
        	root = nodes.get(0);
        	storeN.add(root);
        	
    	}
    	catch (FileNotFoundException exception) {
    		
    		exception.printStackTrace();
    		System.exit(0);
    		
    	}
    	
    }

    // This is the important part - we have to nominate a source node
    // from which all paths are calculated, or the algorithm won't work.

    public void computeShortestPaths(NetworkNode sourceNode) {
    	// copy nodes to a queue
    	    for(int i = 1; i < nodes.size(); i++) {
    		//System.out.println("Nodes are " + nodes.get(i).nameOfNode);
    		    copyNodes.add(nodes.get(i));
    	    }
    	while(storeN.size() != numOfNodes ) {
    		
    	    
    	    
    		// find the minimum D(v)
    		if(!storeN.contains(copyNodes.element())) {
    			
    			storeN.add(copyNodes.element());
    			//System.out.println(copyNodes.element().nameOfNode + " distance is " + copyNodes.element().getDistance());
    		}else {
    			
    			copyNodes.remove();
    			
    		}
    		
    		
    		// debugging
    		if(debugging){
    			for(int i = 0; i < storeN.size(); i++) {
    			    System.out.println("StoreN nodes are: " + storeN.get(i).nameOfNode);
    		    }
    		}
    		
    		// update the D(v)
    		String name = storeN.get(storeN.size()-1).nameOfNode;
    		for(int i = 1; i < nodes.size(); i++) {
    			
    			NetworkLink nl = nodes.get(i).getLink(name);
    			
    			if( !storeN.contains(nodes.get(i)) && nl.containsNode(name) ){
    				
    				double w = nl.getWeight();
    				double oldDis = nodes.get(i).getDistance();
    				double newD = Math.min(oldDis,storeN.get(storeN.size()-1).getDistance() + w);
    				nodes.get(i).setDistance(newD);
    				
    				// update the previous node
    				if(newD < oldDis){
    				
    			    	nodes.get(i).setPreviousNode(storeN.get(storeN.size()-1));
    			    	//System.out.println(" update " + nodes.get(i).nameOfNode + " 's previousnode is " + nodes.get(i).getPreviousNode().nameOfNode);
    				}
    				
    		    }
    	    	
    		}
    		
    	}
    	
    }

    // This should display all of the final network paths and weights
    // in the format given in the assignment.

    public void displayFinalNetwork() {
    	
    	for(int i = 1; i < storeN.size(); i++) {
    		System.out.println("To: " + storeN.get(i).nameOfNode + " is " + storeN.get(i).getDistance() + " routing through " + storeN.get(i).getPreviousNode().nameOfNode);
    	}
    	
    }
    
    
    	
}