Dijkstra algorithm

I'm implementing Dijkstra's algorithm but hasnt found a headwa

Page 1 of 1

9 Replies - 28211 Views - Last Post: 11 November 2008 - 02:04 AM Rate Topic: -----

#1 kwasiimma  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 4
  • Joined: 10-November 08

Dijkstra algorithm

Post icon  Posted 10 November 2008 - 09:15 PM

import java.io.RandomAccessFile;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.NoSuchElementException;

import java.io.*;
import java.util.Scanner;
import javax.swing.*;

public class routing{
		public static void main( String args[] ){
		routing ob=new routing();
		ob.dijkstra();
		
		}


		public void dijkstra( ){
						
			int graph[][] ={
				{0,1,2,5,0,0}, 
				{7,0,2,3,1,0}, 
				{3,2,0,3,0,0}, 
				{0,3,6,0,1,5},
				{0,1,0,1,0,2}, 
				{0,0,0,8,4,0} 
				 
			};
				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 = 1000, 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 = 1000;
				}



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


This post has been edited by born2c0de: 10 November 2008 - 11:25 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Dijkstra algorithm

#2 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8378
  • View blog
  • Posts: 31,956
  • Joined: 06-March 08

Re: Dijkstra algorithm

Posted 10 November 2008 - 09:19 PM

So the question is ?
- code does not compile (what error(s) do you have ?)
- code compiles but generates a run time error (which error ?)
- code runs but do not have the expected behaviour (what do you expect ?)

Please in the future use the [ code] tags ... :code: Makes it easier for us to cut & paste it
I'll edit your post this time

This post has been edited by pbl: 10 November 2008 - 09:22 PM

Was This Post Helpful? 0
  • +
  • -

#3 TriggaMike  Icon User is offline

  • Using up all your 1's and 0's
  • member icon

Reputation: 85
  • View blog
  • Posts: 1,103
  • Joined: 26-September 08

Re: Dijkstra algorithm

Posted 10 November 2008 - 09:22 PM

pbl beat me to the punch...

uhhh, you can remove this post.

This post has been edited by TriggaMike: 10 November 2008 - 09:23 PM

Was This Post Helpful? 0
  • +
  • -

#4 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8378
  • View blog
  • Posts: 31,956
  • Joined: 06-March 08

Re: Dijkstra algorithm

Posted 10 November 2008 - 09:29 PM

TriggaMike: I love to decipher code with so many comments :D
What about you ?

Wikipedia told me that despite his name Dijkstra was a Dutch computer scientist
but I would have like to avoid to search Wikipedia to have the searched algorithm

If it is in Wikipedia I do not thing the topic desserve the "Advanced" tag

This post has been edited by pbl: 10 November 2008 - 09:31 PM

Was This Post Helpful? 0
  • +
  • -

#5 TriggaMike  Icon User is offline

  • Using up all your 1's and 0's
  • member icon

Reputation: 85
  • View blog
  • Posts: 1,103
  • Joined: 26-September 08

Re: Dijkstra algorithm

Posted 10 November 2008 - 09:32 PM

Yeah, I get the whole "Look at my code and tell me why it doesn't work" a lot, but usually it's on simpler things that I have a firm understanding of hahahahaha
Was This Post Helpful? 0
  • +
  • -

#6 kwasiimma  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 4
  • Joined: 10-November 08

Re: Dijkstra algorithm

Posted 11 November 2008 - 01:38 AM

IT COMPILE AND GIVES THIS OUTPUT.
-1 5 4 4 0 0
0 0 0 1 0 0
Was This Post Helpful? 0
  • +
  • -

#7 Gloin  Icon User is offline

  • Expert Schmexpert...
  • member icon

Reputation: 235
  • View blog
  • Posts: 4,489
  • Joined: 04-August 08

Re: Dijkstra algorithm

Posted 11 November 2008 - 01:39 AM

The Dijkstra algorithm efficiently finds the shortest path to each node in a graph using a priority queue version called a heap.

What it does is, originating in a start node S, determines all adjacent nodes and sort them in order of shortest distance (lowest weights on the edges between S and each node in Sa (where Sa is the set of adjacent nodes)). Then it marks the node with the shortest distance (Node T) as visited and determines all it's adjacent nodes that are not marked visited, calculates the distance from S to the nodes adjacent to T using the path through T (I.e distance(S,T) + distance(T, Ta)). If a path to a node in Sa is found that is shorter than before then the distance is updated. Any new node is added to Sa and the set is again sorted. You continue this way, always working with the node that is closest to S and still unvisited until there are no more unvisited nodes. When done, you have found the shortest path to every node in the graph.

You don't need a heap for this but it efficiently handles the nodes and helps you keep track of the visited nodes by removing them from the heap. It's probably harder to implement the heap than keeping track on your own though.

This post has been edited by Gloin: 11 November 2008 - 01:42 AM

Was This Post Helpful? 0
  • +
  • -

#8 kwasiimma  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 4
  • Joined: 10-November 08

Re: Dijkstra algorithm

Posted 11 November 2008 - 01:50 AM

Sorry guys but i need to get this algorithm working. i know little of java that is why i thought this was advanced for me, didnt know it was begger's codes. can you guys help me run the codes?

View PostGloin, on 11 Nov, 2008 - 12:39 AM, said:

The Dijkstra algorithm efficiently finds the shortest path to each node in a graph using a priority queue version called a heap.

What it does is, originating in a start node S, determines all adjacent nodes and sort them in order of shortest distance (lowest weights on the edges between S and each node in Sa (where Sa is the set of adjacent nodes)). Then it marks the node with the shortest distance (Node T) as visited and determines all it's adjacent nodes that are not marked visited, calculates the distance from S to the nodes adjacent to T using the path through T (I.e distance(S,T) + distance(T, Ta)). If a path to a node in Sa is found that is shorter than before then the distance is updated. Any new node is added to Sa and the set is again sorted. You continue this way, always working with the node that is closest to S and still unvisited until there are no more unvisited nodes. When done, you have found the shortest path to every node in the graph.

You don't need a heap for this but it efficiently handles the nodes and helps you keep track of the visited nodes by removing them from the heap. It's probably harder to implement the heap than keeping track on your own though.


how do i keep track of the node then?

Thank you for the contribution, but how do i keep track of the visited nodes?
Was This Post Helpful? 0
  • +
  • -

#9 Gloin  Icon User is offline

  • Expert Schmexpert...
  • member icon

Reputation: 235
  • View blog
  • Posts: 4,489
  • Joined: 04-August 08

Re: Dijkstra algorithm

Posted 11 November 2008 - 01:57 AM

I agree, this is not exactly a beginners problem. Knowing a thing or two about graph-representation certainly helps in this case.

int graph[][] ={  
				{0,1,2,5,0,0},   
				{7,0,2,3,1,0},   
				{3,2,0,3,0,0},   
				{0,3,6,0,1,5},  
				{0,1,0,1,0,2},   
				{0,0,0,8,4,0}   
				   
			};  



The above is your distance matrix. The diagonal 0's indicate each nodes distance to itself. Every other value represent the distance from node a to node b.

If I were you, I would start by renaming the arrays and use names that better represent what they're storing. I assume one of them is initialized 1000 and gets updated as a shorter path is found (might call it temporaryShortestPath). Another array might store the shortest distance once determined, this array could be int or boolean depending on which you prefer (call it determinedShortestPath). Try to reduce the risc of making mistakes using the wrong array.

Simply follow my directions from the previous post and this should hopefully work out for you.

Edited: Use a boolean array to keep track of visited nodes. Remember that it should only be updated when a shortest path has been determined.

boolean[] isVisited = new boolean[NumberOfNodes]; <-- Initialize to false

This post has been edited by Gloin: 11 November 2008 - 02:05 AM

Was This Post Helpful? 0
  • +
  • -

#10 kwasiimma  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 4
  • Joined: 10-November 08

Re: Dijkstra algorithm

Posted 11 November 2008 - 02:04 AM

Quote

i will try using your suggestions and see whats comes up.

Was This Post Helpful? 1
  • +
  • -

Page 1 of 1