networknode.java

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

import java.util.*;

public class NetworkNode implements NodeInterface {
	    public String nameOfNode;
	    private double disV;
	    private NetworkNode pre;
	    ArrayList<NetworkLink> links = new ArrayList<NetworkLink>();
    
    // constructor
    // initialisation the nodes
    public NetworkNode(String name, double dv) {
    	
    	this.nameOfNode = name;
    	this.disV = dv;
    	
    }
    
    // add a link
    
    public void addLink(NetworkLink newLink) {
    	
    	links.add(newLink);
    	//System.out.println("newlink is added " + links.get(links.size()-1).getWeight());
    	
    }

    // We represent D(v) as a distance stored in the node.
    // Providing we use the same u, this is valid.

    public void setDistance(double newDistance) {
    	
    	disV = newDistance;
    	
    }

    public double getDistance() {
    	
    	return disV;
    	
    }

    // This keeps track of the node that is immediately previous to us
    // on the path back to the source node.

    public void setPreviousNode(NetworkNode newPrev) {
    	
    	pre = newPrev;
    	
    }

    public NetworkNode getPreviousNode() {
    	
    	return pre;
    	
    }

    // Required by Comparable.
    // (A number of handy Java data structures use Comparable)
	    
    public int compareTo(NetworkNode o) {
    	
    	if(this.getDistance() - o.getDistance() == 0) {
    		return 0;
    	}else if(this.getDistance() - o.getDistance() > 0) {
    		return 1;
    	}else{
    		return -1;
    	}
    	
    }
    
    public NetworkLink getLink(String from) {
    	
    	int pos = 0;
    	for(int i = 0; i < links.size(); i++) {
    		
    		if(from.equals(links.get(i).getFromNode()) || from.equals(links.get(i).getToNode()) ) {
    			pos = i;
    		}
    		
    	}
    	return links.get(pos);
    	
    }
    
    public String toString() {
    	String res = "";
    	for(int i = 0; i < links.size(); i++) {
    		res += "Node " + nameOfNode + "'s links are " + links.get(i).getFromNode() + " , " + links.get(i).getToNode() + " , " + links.get(i).getWeight() + "\n";
    	}
    	res += " size is " + links.size();
    	return res;
    }
    
   
    
}