awd.java

简易的具有GPS导航功能的程序。仅有四个点

public class AWD 
{
    int NoEdge;  // used for absent edge
    int n;     // number of vertices
    int e;     // number of edges
    int [][]a;     // 2D array

    public AWD(int Vertices ,int noEdge )
    {
    	n = Vertices;
    	e = 0;
        NoEdge = noEdge;
    	a=new int[n+1][n+1];
    	 // initalize to graph with no edges
    	 for (int i = 1; i <= n; i++)
    	    for (int j = 1; j <= n; j++)
    	       a[i][j] = NoEdge;
    }
    public int Exist(int i, int j) 
    {
    	if (i < 1 || j < 1 || i > n || j > n
    		     || a[i][j] == NoEdge) return 0;
    	 return 1;
    }
    public int Edges()  
       {
    	return e;
    	}
    public int Vertices()  
       {
    	return n;
    	}
    public void Add(int i, int j, int w)
    {
    	if (i < 1 || j < 1 || i > n ||
    		     j > n || i == j || a[i][j] != NoEdge)
    		    System.out.println("Vertices not exist.");
    		 else
    		 {
    			   a[i][j] = w;
    			   e++;
    		 }
    }
    public void Delete(int i, int j)
    {
    	if (i < 1 || j < 1 || i > n ||
    		     j > n || a[i][j] == NoEdge)
    		System.out.println("Vertices not exist.");
    		else
    		{
    			  a[i][j] = NoEdge;
    			  e--;
    		}
    }
    public int OutDegree(int i) 
   {
     if (i < 1 || i > n) 
    	 {System.out.println("Vertices not exist.");return 0;}
     int sum = 0;
     for (int j = 1; j <= n; j++)
       if (a[i][j] != NoEdge) sum++;
     return sum;
    }
    public int InDegree(int i) 
    {
    	if (i < 1 || i > n) 
    		{System.out.println("Vertices not exist.");return 0;}
    	 int sum = 0;
    	 for (int j = 1; j <= n; j++)
    	    if (a[j][i] != NoEdge) sum++;
    	 return sum;
    }
    public void Output() 
    {
    	for (int i = 1; i <= n; i++) 
    	{
    	    for (int j = 1; j <= n; j++)
    	    	System.out.print(a[i][j] + " ");
    	    System.out.println();  
    	 }
    }
    public int SortPath(int s,int t,int d[],int p[])
    {		
    	Chain L=new Chain();
    	ChainInterator l=new ChainInterator();
		if(s<1||s>n)
    		{System.out.println("Vertices not exist.");}
		for(int i=1;i<=n;i++)
    	{		
    		d[i]=a[s][i];
    		if(d[i]==NoEdge)p[i]=0;
    		else
    		{
    			p[i]=s;
    			L.Insert(0, i);
    		}
    	}
		while(L.IsEmpty()==0)
    	{	int v=l.Set(L);
    		int w=l.Next();
    		
    		while(w!=0)
    		{
    			if(d[w]<d[v])v=w;
    			w=l.Next();
    		}
    		int i=v;
    		L.Delete(v,i);
    		for(int j=1;j<=n;j++)
    		{
    			if(a[i][j]!=NoEdge&&(p[j]==0||d[j]>d[i]+a[i][j]))
    			{
    				d[j]=d[i]+a[i][j];
    				if(p[j]==0)L.Insert(0, j);
    				p[j]=i;
    			}
    		}
    	}
		if(d[t]>=NoEdge)return 0;
		else return 1;
    }
}