

DIJKSTRA ALGORITHM IN JAVA
11
What is Dijkstra Algorithm? click on the link above and first understand what the algorithm is all about. in short it calculates the shortest path from A to F or vise versa. This code i can guarantee is the simplest and easiest code to understand. just search on google and try to compare this code and other dijkstra code and you will see what i am talking about. i spent alot of time myself and my instructor to guide me on the rite path.
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm(Description)
to see how the algorithm really works go on this website it tells you step by step how to update the cost and which path to choose.
http://renaud.waldura.com/doc/java/dijkstra/
Please give some time to understand the algorithm first and then you can see my code. if you done understand the algorithm it is very useless. i know alot of people need Dijkstra algorithm in java for their HW assignment or Test. i am giving you the solution step by step. anyone who wants to understand please go to the url i have posted above and once you have understand then run the code and for those people who just want to copy so that they can get 90% in their test No Problem Here it is .
First open a notepad and name that file anything like data.txt or datas.txt and make sure the file looks something like this and in this format.
0 3 100 5 100 100 (100 represents infinity)
3 0 6 7 7 100
100 6 0 5 5 3
5 7 5 0 1 100
100 7 5 1 0 2
100 100 3 100 2 0
i name this file as a data.txt file. i have 6 nodes. and A is always the starting node which has the cost of 0 so by looking at the first line i
know that A to A have distance 0, A to B is 3, A to c is Infinity, A to D is 5, A to E is Infinity(means no edge connected with A), A to F is Infinity.
for second line(B to A is 3, and then vise versa) and for the 3rd line it starts for C and etc..
save the txt file by any name and then copy the code which i have posted and then to run type this:
javac routing.java
java routing data.txt
you will get the output. i will say this one more time understand how the algorithm works or ......................
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm(Description)
to see how the algorithm really works go on this website it tells you step by step how to update the cost and which path to choose.
http://renaud.waldura.com/doc/java/dijkstra/
Please give some time to understand the algorithm first and then you can see my code. if you done understand the algorithm it is very useless. i know alot of people need Dijkstra algorithm in java for their HW assignment or Test. i am giving you the solution step by step. anyone who wants to understand please go to the url i have posted above and once you have understand then run the code and for those people who just want to copy so that they can get 90% in their test No Problem Here it is .
First open a notepad and name that file anything like data.txt or datas.txt and make sure the file looks something like this and in this format.
0 3 100 5 100 100 (100 represents infinity)
3 0 6 7 7 100
100 6 0 5 5 3
5 7 5 0 1 100
100 7 5 1 0 2
100 100 3 100 2 0
i name this file as a data.txt file. i have 6 nodes. and A is always the starting node which has the cost of 0 so by looking at the first line i
know that A to A have distance 0, A to B is 3, A to c is Infinity, A to D is 5, A to E is Infinity(means no edge connected with A), A to F is Infinity.
for second line(B to A is 3, and then vise versa) and for the 3rd line it starts for C and etc..
save the txt file by any name and then copy the code which i have posted and then to run type this:
javac routing.java
java routing data.txt
you will get the output. i will say this one more time understand how the algorithm works or ......................
import java.io.RandomAccessFile;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.NoSuchElementException;
public class routing{
public static void main( String args[] ){
routing app = new routing( args[ 0 ] );
}
public routing( String inFile ){
try{
RandomAccessFile file = new RandomAccessFile( inFile, "rw" );
String tmp = file.readLine(); int i = 0;
while( tmp != null ){ tmp = file.readLine(); i++; }
file.seek( 0 ); tmp = file.readLine();
int graph[][]; graph = new int[ i ][ i ]; i = 0;
while( tmp != null ){
StringTokenizer sT = new StringTokenizer( tmp, " " ); int j = 0;
while( sT.hasMoreTokens() ){ graph[ i ][ j++ ] = Integer.parseInt( sT.nextToken() ); }
i++; tmp = file.readLine();
}
file.close();
dijkstra( graph );
}
catch( IOException io ){ System.err.println( io.toString() ); System.exit( 1 ); }
catch( RuntimeException re ){ System.err.println( re.toString() ); System.exit( 1 ); }
}
public void dijkstra( int graph[][] ){
int d[] = new int[ graph.length ];
int dC[] = new int[ graph.length ];
int p[] = new int[ graph.length ];
for( int i = 0; i < graph.length; i++ ){ d[ i ] = 100; dC[ i ] = 100; p[ i ] = 1; }
d[ 0 ] = 0; dC[ 0 ] = 0;
int i = 0, min = 200, pos = 0; //You can change the min to 1000 to make it the largest number
while( i < graph.length ){
//extract minimum
for( int j = 0; j < dC.length; j++ ){
if( min > d[ j ] && dC[ j ] != 1 ){
min = d[ j ]; pos = j;
}
}
dC[ pos ] = 1;
//relax
for( int j = 0; j < graph.length; j++ ){
if( d[ j ] > graph[ pos ][ j ] + d[ pos ] ){
d[ j ] = graph[ pos ][ j ] + d[ pos ];
p[ j ] = pos;
}
}
i++; min = 200;
}
for( int j = 0; j < p.length; j++ ){
System.out.print( p[ j ] + " " );
}
System.out.print( "\n" );
for( int j = 0; j < d.length; j++ ){
System.out.print( d[ j ] + " " );
}
System.out.print( "\n" );
}
}
Comments
Voting
__________________________________________________________
"Programming today is a race between software engineers striving to build bigger and better idiotproof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning."  Rich Cook
I've got good news, and I've got bad news:
The universe is merely a figment of my imagination.
Now are you ready for the bad news?
Late
I've got good news, and I've got bad news:
The universe is merely a figment of my imagination.
Now are you ready for the bad news?
What's so hard about admitting a mistagged snippet?
It's over now!
java routing data.txt , where do i put them??
when i place them at the end of the code, and compile it, it writes me:a class or interface expected...plz let me know the fastest you can, cause i have a problem...thanks...
thanks loads
I am trying to run the java application under eclipse. I created a file data.txt on my desktop. I cant seem to get it working. i changed the code a little. What is this needed for?
routing app = new routing( args[ 0 ] );
It would be great if someone could tell me what i am doing wrong, and why i cant get it to work.
thank you
public static void main( String args[] ){ routing app = new routing( args[ 0 ] ); } public routing(String File){ try{ File file1 = new File("/Desktop/data.txt"); RandomAccessFile file = new RandomAccessFile(file1, "rw" );
I understand dijkstra's algorithm. However, i am having difficulty understanding the output of this program. Can you please explain the output of this program.
Any help is much appreciated. thank you.
0 > 3 > 4 > Finished
/**
* Prints route from source to destination.
* @param p Table with predecessor of every vertex.
* @param source Source vertex.
* @param destination Destination vertex.
*/
public void showRoute(int[] p, int source, int destination) {
int pLength = p.length;
int[] trace = new int[pLength];
int pos = pLength  1;
for (int i = 0; i < pLength; i++) {
trace[ i ] = 1;
}
for (int i = destination; i != source; i = p[ i ]) {
if (i == pLength + 1) {
System.out.println(
"nonexistent (because the graph is not connected).");
return;
} else {
trace[pos] = i;
}
pos;
}
trace[pos  1] = source;
System.out.println("Route from " + source + " to " + destination + ": ");
for (int i = 0; i < trace.length; i++) {
System.out.print((trace[ i ] != 1 ? trace[ i ] + " > ": ""));
}
System.out.println("Finished");
}
Shortest Path Algorithm
1. Input to the algorithm is the N×N matrix that is the distance matrix generated at the start of the algorithm.
2. Define an array that will store the distance and a matrix that will store the whole route.
3. Generate the neighbor list for the source node and put in the matrix
4. Starting from the first neighbor generate the next neighbor.
5. Check if that neighbor already exist in the list if yes than it is a loopback and goto step5
6. Generate the route from all the neighbors for the destination and continue on that path.
7. Generate the route to destination from all neighbors where ever possible.
8. Compare the route length generated by all the possible routes. Compare all the routes in the distance matrix and choose the path to destination which has the lowest path length.
9. If there is no route possible to destination then print not found and exit else print the path which has lowest path length.
The shortest path algorithm is the basis for finding out the alternative path. The output path that is being generated after running the shortest path algorithm is being passed to the alternate path algorithm that generates the alternative path.
1. Establish a network for any number of nodes.
2. Generate an N×N matrix and initialize all the elements of matrix with 0.
3. Calculate the distance from one node to all other nodes and store in an N×N matrix.
4. Give the range of the network node and set all other elements that are outside the range to 0.
5. for (i=0;i