A little help needed with Dijkstra's algorithim


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 2 of 2

Thread: A little help needed with Dijkstra's algorithim

  1. #1
    Join Date
    Apr 2006
    Posts
    5

    A little help needed with Dijkstra's algorithim

    Hi I'm trying to implement Dijkstra's algorithm. I have a class GraphMaker
    which creates the graph, and is the main console. And then a second class for Dijkstra's algorithm. Overall it works alright but, I can't to figure out how to get it to find the shortest path for all the cities.

    Here's a sample output:

    BOSTON To NEW YORK: Cost of: 22 MIAMI: Cost of: 122
    NEW YORK To MIAMI: Cost of: 50 HONOLULU : Cost of: 422
    DETROIT To CHICAGO: Cost of: 22 PHOENIX: Cost of: 62
    MIAMI To HONOLULU : Cost of: 402
    CHICAGO To
    PHOENIX To
    HONOLULU To DETROIT: Cost of: 302 PHOENIX: Cost of: 102


    [BOSTON ----> ]
    [BOSTON ----> , NEW YORK------>]
    [BOSTON ----> , NEW YORK------>, HAWAII------>, DETROIT------>]
    [BOSTON ----> , NEW YORK------>, MIAMI------>]
    [BOSTON ----> , NEW YORK------>, HAWAII------>,CHICAGO------>]
    [BOSTON ----> , NEW YORK------>, HAWAII------>, PHOENIX------>]
    [BOSTON ----> , NEW YORK------>, HAWAII------>]


    I know its not the most efficient looking output, I'm intermediate coder at best. But at the top you have 7 cities from BOSTON to HONOLULU, and the cities they connect to. Where I'm really having the problem is at the bottom part. It shows the shortest paths from Boston to other the cities. But I want it show not only the shortest paths from Boston but also the shortest paths from the other cities, to their destination.

    Here's my code:

    The GraphMaker Class:

    Code:
    public class GraphMaker {
    
       private int [][]  edges;  // The adjacency matrix
       private Object [] Cities; // Cities
       public static int count;
    
       public GraphMaker (int n) {
          edges  = new int [n][n];
          Cities = new Object[n];
       }
    
    
       public int GetSize() 
       {
       	return Cities.length; 
       	}
    
       public void   SetCities (int vertex, Object label) 
       { 
       	Cities[vertex]=label; 
       	}
       
       public Object GetCities (int vertex)              
       { 
    	   return Cities[vertex]; 
    	   
       }
    
       public void AddEdge  (int source, int target, int w) 
        {
    	   edges[source][target] = w; 
       
       }
       public boolean IsEdge (int source, int target)  
       { 
    	   return edges[source][target]>0; 
    	   
       }
       public void  RemoveEdge (int source, int target)  
       { 
    	   edges[source][target] = 0; 
    	   }
       
       public int GetWeight (int source, int target)  
       { 
    	   return edges[source][target]; 
    	   
       }
    
       public int [] Neighbors (int vertex) {
          count = 0;
          for (int i=0; i<edges[vertex].length; i++) {
    	 if (edges[vertex][i]>0) count++;
          }
          final int[]answer= new int[count];
          count = 0;
          for (int i=0; i<edges[vertex].length; i++) {
    	 if (edges[vertex][i]>0) answer[count++]=i;
          }
          return answer;
       }
    
       public void print () {
          for (int j=0; j<edges.length; j++) {
    	 System.out.print (Cities[j]+"    To    ");
    	 
    	 for (int i=0; i<edges[j].length; i++) {
    	    if (edges[j][i]>0) System.out.print (Cities[i]+":  Cost of: " +
    	    		  "   " + edges[j][i]+"    ");
    	  
    	 }
    	 System.out.println (" ");
          }
         
       }
    
       public static void main (String args[]) {
          GraphMaker t = new GraphMaker (7);
          t.SetCities (0, "BOSTON");
          t.SetCities(1, "NEW YORK");
          t.SetCities (2, "DETROIT");
          t.SetCities (3, "MIAMI");
          t.SetCities (4, "CHICAGO");
          t.SetCities (5, "PHOENIX");
          t.SetCities (6, "HAWAII");
          t.AddEdge (0,1,22);
          t.AddEdge (1,6,422);
          t.AddEdge (0,3,122);
          t.AddEdge (2,4,22);
          t.AddEdge (2,5,62);
          t.AddEdge (6,5,102);
          t.AddEdge (3,6,402);
          t.AddEdge (6,2,302);
          t.AddEdge (1,3,50);
          
          t.print();
    
          final int [] pred = Dijkstra.dijkstra (t, 0);
          for (int n=0; n<7; n++) {
    	 Dijkstra.PrintPath (t, pred, 0, n);
    	
          }
          
         
       }
    
    }
    And my Dijkstra class

    Code:
    import java.util.LinkedList;
    
    public class Dijkstra {
    
       
       public static int [] dijkstra (GraphMaker G, int s) {
          final int [] dist = new int [G.GetSize()];  // shortest known distance from "s"
          final int [] pred = new int [G.GetSize()];  // the node that preceeds it in the path
          final boolean [] visited = new boolean [G.GetSize()]; // all false initially
    
          for (int i=0; i<dist.length; i++) {
    	 dist[i] = Integer.MAX_VALUE;
          }
          dist[s] = 0;
    
          for (int i=0; i<dist.length; i++) {
          		
          	final int next = SmallestVertex (dist, visited);
          	visited[next] = true;
    
    	
    
          	final int [] n = G.Neighbors (next);
          		for (int j=0; j<n.length; j++) {
          			final int v = n[j];
          			final int d = dist[next] + G.GetWeight(next,v);
          				if (dist[v] > d) {
          					dist[v] = d;
          					pred[v] = next;
    	    }
    	 }
          }
          return pred; 
       }
    
       private static int SmallestVertex (int [] dist, boolean [] v) {
          int x = Integer.MAX_VALUE;
          int y = -1;   
          for (int i=0; i<dist.length; i++) {
    	 if (!v[i] && dist[i]<x) {y=i; x=dist[i];}
          }
          return y;
       }
    
       public static void PrintPath (GraphMaker G, int [] pred, int s, int e) {
          final LinkedList path = new LinkedList();
          int x = e;
          while (x!=s) {
    	 path.add (0, G.GetCities(x) + "------>");
    	 x = pred[x];
          }
          
         path.add (0, G.GetCities(s) + " ----> ");
         
         
          System.out.println (path);
          
       }
    
    }
    Can somebody point out something I may be missing, or screwing up, the preventing me from getting the results I want.

    Thanks alot

  2. #2
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    You "just" need to start your route from a different node, then discover your shortest route to every destination which can be reached from that starting node. Perform a path discovery first, so you know all of the starting points and ending points possible in your network. Calculate your shortest distance for the various point-to-point routes. Store those results. Then, when a given path includes that point-to-point, you've already learned it and don't need to learn it again.

Similar Threads

  1. Replies: 0
    Last Post: 06-12-2006, 04:18 PM
  2. Visual C++/MFC/PL/SQL Guru needed in Philadelphia!!
    By Lisa Osborne in forum Careers
    Replies: 0
    Last Post: 05-02-2002, 12:00 PM
  3. Help! Advanced Multi-Homed Routing needed.
    By Michael Zietlow in forum Open Source
    Replies: 0
    Last Post: 12-07-2000, 04:59 PM
  4. Visual Basic Guru needed - Atlanta
    By Julie Sisson in forum vb.announcements
    Replies: 1
    Last Post: 04-06-2000, 11:06 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center