Shortest path

Hello every one. I have been banging my head with this program. What I need is my printout to be:

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:

Code:

---

Lollardry, scatterling, obstetrist, provaocative

---

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!

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.

Quote:

---

Originally Posted by ozzyman

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.

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

Quote:

---

Originally Posted by ozzyman

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:

Code:

---

Lollardry, scatterling, obstetrist, provaocative

---

I am trying to get my output to look like this:

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

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.

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