DIJKSTRA ALGORITHM IN JAVA





11
Date Submitted Wed. Oct. 25th, 2006 9:57 AM
Revision 1 of 1
Helper fastmike
Tags C | File | Java | String
Comments 18 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" );
        }
}
 

chris mike

Comments

Comments Tags...
Fri. Oct. 27th, 2006 8:28 PM    Beginner alp0001
  Comments And likewise . . .
Thu. Nov. 2nd, 2006 12:56 PM    Scripter sehrgut
    Comments Wrong Tags
Tue. Nov. 7th, 2006 10:10 AM    Helper fastmike
    Comments Grammar
Mon. Nov. 6th, 2006 6:13 PM    Helper fastmike
  Comments idiot!
Sat. Oct. 28th, 2006 7:12 AM    Helper fastmike
    Comments g3t sumM GRa/\/\mar sk1lz
Thu. Nov. 2nd, 2006 12:57 PM    Scripter sehrgut
    Comments Re: idiot!
Mon. Oct. 30th, 2006 9:40 AM    Helper bright
Comments Appreciate the work
Sat. Nov. 18th, 2006 6:01 PM    Newbie guitarfox
Comments Thanks Mike!
Sun. Apr. 1st, 2007 10:36 PM    Newbie dual_barrel
  Comments no problem
Fri. Jun. 1st, 2007 10:48 PM    Helper fastmike
    Comments DIJKSTRA ALGORITHM JAVA
Mon. Dec. 21st, 2009 11:50 AM    Newbie snikol85
Comments Thanks!
Sat. May. 31st, 2008 4:43 AM    Newbie kryptonite
Comments Problem
Thu. Nov. 20th, 2008 12:21 PM    Newbie daniman
Comments output
Thu. Mar. 12th, 2009 2:22 AM    Newbie eceone
  Comments output
Sun. May. 10th, 2009 5:21 PM    Newbie zazzero
    Comments output
Sat. Nov. 14th, 2009 4:12 PM    Beginner bugmenot
Comments can u help ???????????
Mon. Oct. 10th, 2011 5:08 PM    Newbie arjun1910
Comments can u help ?????(contd..)
Mon. Oct. 10th, 2011 5:10 PM    Newbie arjun1910

Voting