simplessp.java

来自「This code implements the shortest path a」· Java 代码 · 共 64 行

public class SimpleSSP {
  // simple schema  
	final int MAX=5000;

    public int n;
    public int length[][]; 
    private int dist[];
    private boolean s[];
 
    public SimpleSSP (AdjGraph G,int nn){
    	n=nn;
    	length =new int [n][n];
        for (int i=0;i<n;i++)
        	for (int j=0;j<n;j++){
        		length[i][j]=G.getWeight(i,j);
        		//read from the adjacent list graph and store the value into the length matrix
        	}
       dist=new int[n];
       s=new boolean[n];
	}
    
	public int[] ShortestPath(int v){
        for(int i=0;i<=n-1;i++){
                s[i]=false;
                dist[i]=length[v][i];
        }
        s[v]=true;
        dist[v]=0;

        for(int i=0;i<n-2;i++){
                int u=choose();  
                // choose the minimum node
                s[u]=true;  
                // if u has been chosen mark it with true
                for(int w=0;w<=n-1;w++){
                        if(!s[w]){
                                if(dist[u]+length[u][w]<dist[w]){
                                	// if the current cost is less than history
                                        dist[w]=dist[u]+length[u][w]; 
                                        // update the dist[]
                                }
                        }
                }
        }
        return dist;
	}

	public int choose(){  
		// choose the minimum node in the graph
        int temp=MAX;
        int index=0;
        for(int i=0;i<=n-1;i++){
                if(s[i]==false&&dist[i]<=temp){
                        temp=dist[i];
                        index=i;
                }
        }
        return index;
	}

}