Results 1 to 6 of 6
Thread: Shortest path
- 03-23-2012, 05:04 AM #1
Member
- Join Date
- Mar 2012
- Posts
- 5
- Rep Power
- 0
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
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 05:28 AM.
-
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.
- 03-23-2012, 05:22 AM #3
Member
- Join Date
- Mar 2012
- Posts
- 5
- Rep Power
- 0
-
Re: Shortest path
Where -what- was? You didn't tell us anything about any error messages, compile problems or your current output.
- 03-23-2012, 05:36 AM #5
Member
- Join Date
- Mar 2012
- Posts
- 5
- Rep Power
- 0
Re: Shortest path
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
Java Code:436 Lollardry 236 scatterling 131 obstetrist 69 provocative
Java Code:System.out.println(map.getRoute("Lollardry", "provocative"));
- 03-23-2012, 10:25 AM #6
- Join Date
- Sep 2008
- Location
- Voorschoten, the Netherlands
- Posts
- 14,422
- Blog Entries
- 7
- Rep Power
- 29
Similar Threads
-
implementing an algorithm for shortest path problem in java
By thorobred in forum New To JavaReplies: 0Last Post: 03-20-2011, 01:17 AM -
Shortest Seek-Time First with java.util.concurrent
By SAiNT_JiMMiE in forum Threads and SynchronizationReplies: 0Last Post: 05-11-2010, 10:18 AM -
setting class-path & Library Path in ubantu
By programmer_007 in forum EclipseReplies: 18Last Post: 02-22-2010, 12:31 PM -
Help with a Graph Data Structure and the Shortest Path
By rhm54 in forum New To JavaReplies: 1Last Post: 03-21-2008, 03:14 PM
Bookmarks