Snippets

Home / Snippets / DIJKSTRA ALGORITHM IN JAVA

DIJKSTRA ALGORITHM IN JAVA

Snippet Menu

snippet |

revisions |

comments | Related Snippets

related |

Add to Favorites | Email

download | Print

print | Blog It

blog it

Wed. Oct. 25th, 2006 9:57 AM

1 of 1

fastmike

C | File | Java | String

11 comments

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

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

        }

}