Thread: 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.

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.

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.

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

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

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.

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.

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.

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?

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

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

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.

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?

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?

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.

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