Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

1. ## 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:
```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:
```import java.io.File;
import java.io.FileNotFoundException;
import java.util.Iterator;
import java.util.Scanner;

/**
* @author Clint Sharp
*/
public class dijkstra {
int numberOfNodes=0;

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);}

for(int i=0; i<numberOfNodes;i++){
cur=file.nextLine();
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)){
}
}

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:
```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!

2. ## 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.

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.

3. ## Re: Dijkstra's code help

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:
`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:
`System.out.println(map.getRoute("Lollardry", "provocative"));`
and the output is as follows:
`Lollardry, scatterling, obstetrist, provocative`

4. ## 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.

5. ## Re: Dijkstra's code help

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:
`Lollardry, scatterling, obstetrist, provocative`
where "Lollardry" is the starting point and "provacative" is my end point.

What I would like to have is:
`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.

6. ## Re: Dijkstra's code help

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

7. ## Re: Dijkstra's code help

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:
```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 "";
}```

8. ## 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.

9. ## Re: Dijkstra's code help

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?

10. ## Re: Dijkstra's code help

Start by changing this:
```        //public String toString(){
//return place + " " +weight;
//}```
to this:
```   public String toString(){
return "<"+place + " " +weight + ">";
}```

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

11. ## Re: Dijkstra's code help

Originally Posted by Norm
Start by changing this:
```        //public String toString(){
//return place + " " +weight;
//}```
to this:
```   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
```System.out.println(toString());
&
System.out.println(NodeData.toString());```
and neither work. I am just trying to see what its output would be.

12. ## 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?

13. ## Re: Dijkstra's code help

I did this and it prints exactly what was listed above. No numbers just the "city" names.
`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

14. ## 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().

15. ## 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
`Lollardry, scatterling, obstetrist, provocative`
I would like to have it print:
`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
```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
```import java.io.File;
import java.io.FileNotFoundException;
import java.util.Iterator;
import java.util.Scanner;

/**
* @author Clint Sharp
*/
public class dijkstra {
int numberOfNodes=0;

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);

for(int i=0; i<numberOfNodes;i++){
cur=file.nextLine();
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)){
//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
```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.

16. ## Re: Dijkstra's code help

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?

17. ## Re: Dijkstra's code help

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?

18. ## 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:
`  return shortestPath[i].path;`

When you build the contents of path, you need to add in the distances.

19. ## 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 (").