# Dijkstra's code help

• March 21st, 2012, 12:29 PM
csharp100
Dijkstra's code help
Hello everyone,
I have the following code for Dijkstra's algorithm. What my problem is how to get from a start node to ALL the nodes. If I have 4 nodes say STL, NY, CHI, & ATL all with different weights and my start node is STL, then I need to figure the shortest distance from STL to NY, STL to CHI and STL to ATL. There could be a weight between STL & CHI of 250 miles and 275 miles. My other problem is trying to get the distances printed along with the city names. I got the city names to print but not the distances. If anyone can help I could appreciate. Code would be nice! Thanks everyone!
Test file:
Code :

```public class test {   public static void main(String args[]) throws FileNotFoundException { //for (int i = 0; i<=args.length-1; i++){ File file = new File("test1.dat");   dijkstra map = new dijkstra(file);   //Scanner input = new Scanner(args[i+1]);     //int choice = input.nextInt();   //switch (choice){ //case 0: //System.out.println(map.toString()); //break;   //case 1: System.out.println(map.getRoute("Lollardry", "provocative")); //System.out.println(map.getRoute("provocative", "pseudolaminated")); //break;   //}   }   }```

dijkstra code:
Code :

```import java.io.File; import java.io.FileNotFoundException; import java.util.Iterator; import java.util.Scanner; import java.util.LinkedList;   /** * @author Clint Sharp */ public class dijkstra { int numberOfNodes=0; LinkedList[] array;   public dijkstra(File map) throws FileNotFoundException{     Scanner file = new Scanner(map);   int pos=0; String cur="";   cur=file.nextLine(); if(pos==0){numberOfNodes=Integer.parseInt(cur);}   array = new LinkedList[numberOfNodes];   for(int i=0; i<numberOfNodes;i++){ cur=file.nextLine(); LinkedList list = new LinkedList(); list.add(new NodeData(cur,0)); array[i]=list; }   while(file.hasNextLine()){   cur=file.next(); //System.out.println("Start "+cur); String start = cur;   cur=file.next(); //System.out.println("End "+cur); String end = cur;   cur=file.next(); //System.out.println("Weight "+cur); String weightString = cur; int weight = Integer.parseInt(weightString);     for(int i=0; i<numberOfNodes; i++){ if(((NodeData)array[i].getFirst()).place.equals(start)){ array[i].add(new NodeData(end, weight)); } }   if(file.hasNextLine()){ file.nextLine(); }     }   }     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; tmp.weight=tmp.weight+cur.weight; tmp.path=cur.path+", "+tmp.place; if(tmp.weight<placesToGo[posIfPresent].weight){ placesToGo[posIfPresent]=tmp; }   else{ placesToGo[posIfPresent].weight+=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)){ 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(){}     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; //}     }   }```

test1.dat file:
Code :

```15 congelative expugn externization flier frontsman harpylike hydrochlorplatinic Lollardry nonstriped obstetrist picamar provocative pseudolaminated scatterling unreefed Lollardry expugn 59 Lollardry scatterling 236 expugn expugn 168 expugn harpylike 208 externization obstetrist 80 externization scatterling 34 externization unreefed 185 flier unreefed 8 frontsman expugn 112 frontsman unreefed 138 harpylike harpylike 144 harpylike hydrochlorplatinic 148 hydrochlorplatinic Lollardry 124 hydrochlorplatinic expugn 136 hydrochlorplatinic externization 145 hydrochlorplatinic provocative 76 nonstriped scatterling 129 obstetrist frontsman 207 obstetrist harpylike 135 obstetrist hydrochlorplatinic 61 obstetrist nonstriped 189 obstetrist obstetrist 204 obstetrist provocative 69 picamar expugn 72 picamar flier 49 picamar harpylike 121 picamar obstetrist 119 provocative pseudolaminated 144 pseudolaminated frontsman 74 pseudolaminated hydrochlorplatinic 127 pseudolaminated nonstriped 193 pseudolaminated scatterling 23 scatterling obstetrist 131 unreefed provocative 127```

Thanks again!
• March 21st, 2012, 01:15 PM
Norm
Re: Dijkstra's code help
Do you have a design or algorithm for solving this problem? Given that, someone could help you fix your code so that it follows the algorithm.

Quote:

get the distances printed along with the city names.
Where do you print the city names? Where is the distance value that you want to print with the name?

Can you post what the program prints now and add some comments to it showing what the problem is
and show what you want the output to look like.
• March 21st, 2012, 01:45 PM
csharp100
Re: Dijkstra's code help
Quote:

Originally Posted by Norm
Do you have a design or algorithm for solving this problem? Given that, someone could help you fix your code so that it follows the algorithm.

I'm realizing a different way of Dijkstra needs to written.

Where do you print the city names? Where is the distance value that you want to print with the name?

The algorithm is called from the test program. and prints from:
Code :

`public String getRoute(String begin, String end)`
function. The problem I'm having is getting the actual distance to go along with the city name.

Can you post what the program prints now and add some comments to it showing what the problem is
and show what you want the output to look like.

From the test function I have two cities listed:
Code :

`System.out.println(map.getRoute("Lollardry", "provocative"));`
and the output is as follows:
Code :

`Lollardry, scatterling, obstetrist, provocative`
• March 21st, 2012, 01:55 PM
Norm
Re: Dijkstra's code help
Can you post what the program prints now and add some comments to it showing what the problem is
and show what you want the output to look like.
• March 21st, 2012, 02:11 PM
csharp100
Re: Dijkstra's code help
Quote:

Originally Posted by Norm
Can you post what the program prints now and add some comments to it showing what the problem is
and show what you want the output to look like.

Yes, when I run the program the output is as follows:
Code :

`Lollardry, scatterling, obstetrist, provocative`
where "Lollardry" is the starting point and "provacative" is my end point.

What I would like to have is:
Code :

`436 Lollardry 236 scatterling 131 obstetrist 69 provocative`
where 436 is the total miles from "Lollardry" to "provocative", 236 is the distance from "Lollardry" to "scatterling", 131 is the distance from "scatterling" to "obstetrist", etc.

I figure once I have this down, I can do the rest of the project.
• March 21st, 2012, 02:25 PM
Norm
Re: Dijkstra's code help
Where are those distance values available so you can use them when formatting the String for printing?
• March 21st, 2012, 02:53 PM
csharp100
Re: Dijkstra's code help
Quote:

Originally Posted by Norm
Where are those distance values available so you can use them when formatting the String for printing?

Well that seems to be my problem. The distances are in the linked list array. I guess I have to do a comparison of some sort in order to get the "miles". My return statement from the algorithm is:
Code :

```for(int i=0; i<shortestPath.length; i++){ if(shortestPath[i]!=null && shortestPath[i].place.equals(end)){ //System.out.println(shortestPath[i].path); return shortestPath[i].path; } } return ""; }```
• March 21st, 2012, 03:07 PM
Norm
Re: Dijkstra's code help
Change what is saved in the NodeData class to include what you want to see printed.
For debugging add a toString() method to NodeData that will return useful info to print out.
• March 21st, 2012, 03:24 PM
csharp100
Re: Dijkstra's code help
Quote:

Originally Posted by Norm
Change what is saved in the NodeData class to include what you want to see printed.
For debugging add a toString() method to NodeData that will return useful info to print out.

You lost me there. Do I not have a toString() method in NodeData? Can you help me out with a little code?
• March 21st, 2012, 03:43 PM
Norm
Re: Dijkstra's code help
Start by changing this:
Code :

``` //public String toString(){ //return place + " " +weight; //}```
to this:
Code :

``` public String toString(){ return "<"+place + " " +weight + ">"; }```

Then add more variables to the returned String like path or what ever you want to see.
• March 21st, 2012, 03:55 PM
csharp100
Re: Dijkstra's code help
Quote:

Originally Posted by Norm
Start by changing this:
Code :

``` //public String toString(){ //return place + " " +weight; //}```
to this:
Code :

``` public String toString(){ return "<"+place + " " +weight + ">"; }```

Then add more variables to the returned String like path or what ever you want to see.

Dang this Java! I changed it like you said, ran the program and nothing changed. Can I not call this method to main? I tired
Code :

```System.out.println(toString()); & System.out.println(NodeData.toString());```
and neither work. I am just trying to see what its output would be.
• March 21st, 2012, 04:01 PM
Norm
Re: Dijkstra's code help
That change was for use when debugging the program. You need to change the code so it calls the toString method and prints out what is returned.
For example print the value of the shortestPath element: shortestPath[i] just before you return its path variable.

Where are the numbers that you want to include in the path's value? How do you get those numbers into the path variable?
• March 21st, 2012, 04:14 PM
csharp100
Re: Dijkstra's code help
I did this and it prints exactly what was listed above. No numbers just the "city" names.
Code :

`System.out.println(shortestPath[i].path);`

I was working on the toString() method and trying to figure where to change the code and to what in order for it to be called. I tried doing it in main just to see what was in it and to no avail
• March 21st, 2012, 04:18 PM
Norm
Re: Dijkstra's code help
Yes it would do exactly the same. I don't think I said to print the path because it was already being printed. Leave off the .path and just print the element which will cause the toString() method to be called.

There will not be any numbers in the print out until you figure out how to get them and write code to put them into the String being returned by getRoute().
• March 22nd, 2012, 09:06 PM
csharp100
Re: Dijkstra's code help
Well back for another run at it. Can anyone at least tell me how to print out the distance with the cities? As the code is set up now, it prints
Code :

`Lollardry, scatterling, obstetrist, provocative`
I would like to have it print:
Code :

`436 Lollardry 236 scatterling 131 obstetrist 69 provocative`
Where 436 is the total miles of the cities visited, 236 is the miles between Lollardry & scatterling 131 is the miles between scatterling & obstetrist, etc.

I have enclosed the latest code which consist of a test.java, dijkstra.java and test1.dat.
test.java
Code :

```import java.io.File; import java.io.FileNotFoundException; import java.util.*;   public class test {   public static void main(String args[]) throws FileNotFoundException { //for (int i = 0; i<=args.length-1; i++){ File file = new File("test1.dat");   dijkstra map = new dijkstra(file);   //Scanner input = new Scanner(args[i+1]);     //int choice = input.nextInt();   //switch (choice){ //case 0: //System.out.println(map.toString()); //break;   //case 1: System.out.println(map.getRoute("Lollardry", "provocative")); //System.out.println(.toString()); //break;   //}   }   }```
Dijkstra.java
Code :

```import java.io.File; import java.io.FileNotFoundException; import java.util.Iterator; import java.util.Scanner; import java.util.LinkedList;   /** * @author Clint Sharp */ public class dijkstra { int numberOfNodes=0; LinkedList[] array;   public dijkstra(File map) throws FileNotFoundException{     Scanner file = new Scanner(map);   int pos=0; String cur="";   cur=file.nextLine(); if(pos==0){numberOfNodes=Integer.parseInt(cur);} //System.out.println(numberOfNodes);   array = new LinkedList[numberOfNodes];   for(int i=0; i<numberOfNodes;i++){ cur=file.nextLine(); LinkedList list = new LinkedList(); list.add(new NodeData(cur,0)); array[i]=list; }   while(file.hasNextLine()){   cur=file.next(); //System.out.println("Start "+cur); String start = cur;   cur=file.next(); //System.out.println("End "+cur); String end = cur;   cur=file.next(); //System.out.println("Weight "+cur); String weightString = cur; int weight = Integer.parseInt(weightString);     for(int i=0; i<numberOfNodes; i++){ if(((NodeData)array[i].getFirst()).place.equals(start)){ array[i].add(new NodeData(end, weight)); //System.out.println(end); //System.out.println(weight); } }   if(file.hasNextLine()){ file.nextLine(); //System.out.println(file.nextLine()); }     }   }     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;   }     }   }```
test1.dat
Code :

```15 congelative expugn externization flier frontsman harpylike hydrochlorplatinic Lollardry nonstriped obstetrist picamar provocative pseudolaminated scatterling unreefed Lollardry expugn 59 Lollardry scatterling 236 expugn expugn 168 expugn harpylike 208 externization obstetrist 80 externization scatterling 34 externization unreefed 185 flier unreefed 8 frontsman expugn 112 frontsman unreefed 138 harpylike harpylike 144 harpylike hydrochlorplatinic 148 hydrochlorplatinic Lollardry 124 hydrochlorplatinic expugn 136 hydrochlorplatinic externization 145 hydrochlorplatinic provocative 76 nonstriped scatterling 129 obstetrist frontsman 207 obstetrist harpylike 135 obstetrist hydrochlorplatinic 61 obstetrist nonstriped 189 obstetrist obstetrist 204 obstetrist provocative 69 picamar expugn 72 picamar flier 49 picamar harpylike 121 picamar obstetrist 119 provocative pseudolaminated 144 pseudolaminated frontsman 74 pseudolaminated hydrochlorplatinic 127 pseudolaminated nonstriped 193 pseudolaminated scatterling 23 scatterling obstetrist 131 unreefed provocative 127```

Please please! I am racking my brain here and getting nowhere. Thanks.
• March 22nd, 2012, 09:10 PM
Norm
Re: Dijkstra's code help
Quote:

how to print out the distance with the cities?
Where are the distance values kept? Where is the printing of the cities done?
Can the location in the code that builds the String with the cities, access the distances and include them with the cities?
• March 22nd, 2012, 09:27 PM
csharp100
Re: Dijkstra's code help
Quote:

Originally Posted by Norm
Where are the distance values kept? Where is the printing of the cities done?
Can the location in the code that builds the String with the cities, access the distances and include them with the cities?

Frankly that is my problem. The System.out.println(map.getRoute("start city", "end city") is in test.java where getRoute is in Dijkstra and returns right back to test.java. The return is the cities. How do I get the miles along with the cities? Would you please show me?
• March 23rd, 2012, 06:26 AM
Norm
Re: Dijkstra's code help
Where are the distance values you want printed?

Is this what is printed and where you want the distances included:
Code :

` return shortestPath[i].path;`

When you build the contents of path, you need to add in the distances.
• March 24th, 2012, 08:15 PM
ziplague
Re: Dijkstra's code help
By the way, you can make the code more readable by inserting it between "highlight=java" & "/highlight" , it will make it more colorful :) just use brackets instead of the (").