Results 1 to 6 of 6

Thread: Shortest path

  1. #1
    csharp100 is offline Member
    Join Date
    Mar 2012
    Posts
    5
    Rep Power
    0

    Default Shortest path

    Hello every one. I have been banging my head with this program. What I need is my printout to be:
    Java Code:
    436 Lollardry 236 scatterling 131 obstetrist 69 provocative
    Where is 436 is the total miles between the 4 cities, 236 is the distance between Lollardry & scatterling 131 is the distance between scatterling & obstetrist, etc.
    My printout now is:
    Java Code:
    Lollardry, scatterling, obstetrist, provaocative

    Java Code:
    public String getRoute(String begin, String end){
    
    	boolean beginFound=false;
    	boolean endFound=false;
    	
    	for(int i=0;i<array.length;i++){
    		if(((NodeData)array[i].getFirst()).place.equals(begin)){beginFound=true;}
    	}
    	
    	for(int i=0;i<array.length;i++){
    		if(((NodeData)array[i].getFirst()).place.equals(end)){endFound=true;}
    	}
    	
    	if(endFound==false || beginFound==false ){throw new IllegalArgumentException();}
    	
    	NodeData[] placesToGo = new NodeData[numberOfNodes];
    	NodeData[] shortestPath = new NodeData[numberOfNodes];
    	int placesToGoSize=0;
    	int placesToGoCounter=0;
    	int shortestPathCounter=0;
    	NodeData cur = new NodeData(begin, 0);
    	cur.path=cur.place;
    	
    	
    	placesToGo[0]=cur; placesToGoCounter++; placesToGoSize++;
    	
    	
    	while(placesToGoSize!=0){
    		int posInDataArray=0;
    		for(int i=0; i<array.length; i++){
    			if(cur.place.equals(((NodeData)array[i].getFirst()).place)){
    				posInDataArray=i;
    				break;
    			}
    		}
    		
    		
    		Iterator iter = array[posInDataArray].iterator();
    		Object trash = iter.next();
    		
    		NodeData tmp = null;
    		
    		while(iter.hasNext()){
    			
    			tmp=((NodeData)iter.next());
    			
    		boolean isPresentInShortestPath=false;
    		for(int i=0; i<shortestPath.length;i++){
    			if(shortestPath[i]!=null && shortestPath[i].place.equals(tmp.place)){
    				isPresentInShortestPath=true;
    			}
    		}
    		
    		if(isPresentInShortestPath==false){
    			int posIfPresent=-1;
    			boolean isPresentInPlacesToGo = false;
    			for(int i=0; i<placesToGo.length;i++){
    				if(placesToGo[i]!=null && placesToGo[i].place.equals(tmp.place)){
    					isPresentInPlacesToGo=true;
    					posIfPresent=i;
    				}
    			}
    			
    			
    			if(isPresentInPlacesToGo==true){
    				int tmpWeight=tmp.weight;
    				//System.out.println("tmp weight" + tmp.weight);
    				tmp.weight=tmp.weight+cur.weight;
    				//System.out.println("tmp weight + cur.weight" + tmp.weight);
    				tmp.path=cur.path+", "+tmp.place;  
    				if(tmp.weight<placesToGo[posIfPresent].weight){
    					placesToGo[posIfPresent]=tmp;
    				}
    
    				else{
    					placesToGo[posIfPresent].weight+=tmpWeight;
    					//System.out.println(tmpWeight);
    					
    				}
    				
    				
    
    			}
    			
    			if(isPresentInPlacesToGo==false){
    				tmp.weight=tmp.weight+cur.weight;
    				tmp.appendToPath(cur.path+", "+tmp.place);
    				placesToGo[placesToGoCounter]=tmp;
    				placesToGoCounter++;
    				placesToGoSize++;
    			}	
    
         }
    		
    
    }
    		
    		int smallest=-1;
    		int smallestPos=-1;
    		for(int i=0; i<placesToGo.length;i++){
    			if(smallest==-1 && placesToGo[i]!=null){
    				smallest=placesToGo[i].weight;
    				smallestPos=i;
    				}
    			if(placesToGo[i]!=null && placesToGo[i].weight<smallest){
    				smallest=placesToGo[i].weight;
    				smallestPos=i;
    				}
    		}
    		
    
    		NodeData smallestData = placesToGo[smallestPos];  
    		
    		placesToGo[smallestPos]=null;
    		placesToGoSize--;
    		
    		shortestPath[shortestPathCounter]=smallestData;
    		shortestPathCounter++;
    		
    		smallest=-1;
    		smallestPos=-1;
    		for(int i=0; i<placesToGo.length;i++){
    			if(smallest==-1 && placesToGo[i]!=null){
    				smallest=placesToGo[i].weight;
    				smallestPos=i;
    				}
    			if(placesToGo[i]!=null && placesToGo[i].weight<smallest){
    				smallest=placesToGo[i].weight;
    				smallestPos=i;
    				}
    		}
    		
    		if(smallestPos!=-1){cur=placesToGo[smallestPos];}
    
    	}
    		
    		
    	for(int i=0; i<shortestPath.length; i++){
    		if(shortestPath[i]!=null && shortestPath[i].place.equals(end)){
    			//System.out.println(shortestPath[i]);
    			return shortestPath[i].path;
    			}
    	}
    	return "";
    }
    
    
    public String toString(){
    	String output="";
    	
    	for(int i=0; i<array.length; i++){
    		output+=i+1;
    		
    		Iterator iter = array[i].iterator();
    		while(iter.hasNext()){
    			output+="-->"+((NodeData)iter.next()).toString();
    		}
    		output+="\n";
    	}
    	
    	return output;
    	
    }
    
    
    
    public class NodeData{
    	
    
    	public NodeData(String placeIn, int weightIn){
    		place=placeIn; 
    		weight=weightIn;
    	}
    	
    	public String place="";
    	public int weight=0;
    	public String path=place;
    	
    	
    	public String getPath(){
    		return path;
    	}
    	
    	public void appendToPath(String appendRoute){
    		path=path+appendRoute;
    	}
    	
    	public void appendWeight(int appendWeight){
    		weight=weight+appendWeight;
    	}
    	
    	public void setWeight(int betterWeight){
    		weight=betterWeight;
    	}
    	
    	public void setPath(String betterRoute){
    		path=place+", "+betterRoute;
    	}
    	public String toString(){
    		return place + " " +weight;
    
    	}
    	
    	
    }
    
    }

    I have been banging my head for a few days and was hoping someone can show me what to do. I would appreciate it and thank!
    Last edited by csharp100; 03-23-2012 at 06:28 AM.

  2. #2
    ozzyman's Avatar
    ozzyman is offline Senior Member
    Join Date
    Mar 2011
    Location
    London, UK
    Posts
    797
    Blog Entries
    2
    Rep Power
    4

    Default Re: Shortest path

    Please edit your incredibly long post, and replace it with a clear, concise question relating to a specific problem or error you are having.

    If you had said, I need my output to be "this" and its currently giving me "that" and I don't understand why. What am I doing wrong?

    Then you have an answerable question.

    But as it stands, all you've said is "This is my homework, please do it for me!!!"

    So it is very unlikely that anyone is going to help you.

    So please, tell us what your current problem is that you need to tackle, and just show us the relevant code so that we don't have to sieve through your entire application to find it.

  3. #3
    csharp100 is offline Member
    Join Date
    Mar 2012
    Posts
    5
    Rep Power
    0

    Default Re: Shortest path

    Quote Originally Posted by ozzyman View Post
    Please edit your incredibly long post, and replace it with a clear, concise question relating to a specific problem or error you are having.

    Seriously? That IS the code I am having troubles with.

    If you had said, I need my output to be "this" and its currently giving me "that" and I don't understand why. What am I doing wrong?

    The only part there missing is "What am I doing wrong." My question was clear and concise. Please reread as opposed to citicizing my post.

    Then you have an answerable question.

    But as it stands, all you've said is "This is my homework, please do it for me!!!"

    This is homework. I amm not asking anyone to write the whole thing. I did that. My problem is it is printing out the shortest path with no miles attached and I am hoping someone can actually point out How I can get the shortest path with the miles attached.

    So it is very unlikely that anyone is going to help you.

    So please, tell us what your current problem is that you need to tackle, and just show us the relevant code so that we don't have to sieve through your entire application to find it.
    If I had a clue as to where is was, believe you me I would have done that.

  4. #4
    ozzyman's Avatar
    ozzyman is offline Senior Member
    Join Date
    Mar 2011
    Location
    London, UK
    Posts
    797
    Blog Entries
    2
    Rep Power
    4

    Default Re: Shortest path

    Where -what- was? You didn't tell us anything about any error messages, compile problems or your current output.

  5. #5
    csharp100 is offline Member
    Join Date
    Mar 2012
    Posts
    5
    Rep Power
    0

    Default Re: Shortest path

    Quote Originally Posted by ozzyman View Post
    Where -what- was? You didn't tell us anything about any error messages, compile problems or your current output.
    Lets try this again. I do not have a compile problem. I do not have error messages. current output is:
    Java Code:
    Lollardry, scatterling, obstetrist, provaocative
    I am trying to get my output to look like this:
    Java Code:
    436 Lollardry 236 scatterling 131 obstetrist 69 provocative
    The problem is I do not know how to do that. In the test program which has now been edited out is a line that reads
    Java Code:
    System.out.println(map.getRoute("Lollardry", "provocative"));
    These are the two "cities" the algorithm finds the shortest path. Where I am having the problem is in the return statement class getPath. I cannot figure how to get the miles attached.

  6. #6
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,778
    Blog Entries
    7
    Rep Power
    21

    Default Re: Shortest path

    Are you applying the Dijkstra Shortest Path algorithm? If so, it should be easy to find the costs/length for a city on the shortest path towards the start of the route (it's in the heap).

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Replies: 0
    Last Post: 03-20-2011, 02:17 AM
  2. Shortest Seek-Time First with java.util.concurrent
    By SAiNT_JiMMiE in forum Threads and Synchronization
    Replies: 0
    Last Post: 05-11-2010, 11:18 AM
  3. setting class-path & Library Path in ubantu
    By programmer_007 in forum Eclipse
    Replies: 18
    Last Post: 02-22-2010, 01:31 PM
  4. Replies: 1
    Last Post: 03-21-2008, 04:14 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •