# Dijkstra's Algorithm: Java Implementation Source Vertex Issues...

Page 1 of 1

## 2 Replies - 13607 Views - Last Post: 09 October 2010 - 08:37 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=194269&amp;s=62526b2af551f53d7b6160542ba16cd1&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 anoneemooz

Reputation: 0
• Posts: 2
• Joined: 09-October 10

# Dijkstra's Algorithm: Java Implementation Source Vertex Issues...

Posted 09 October 2010 - 08:05 PM

Hi I am currently taking up a basic data structures and algorithms course and we're on the topic of Dijkstra's algorithm. Based on sample code online I came up with this:

Dijkstra:
```public class Dijkstra
{

public static int [] dijkstra ( WeightedGraph wg, int s )
{
int [] dist = new int [ wg.size() ];
int [] pred = new int [ wg.size() ];
boolean [] visited = new boolean [ wg.size() ];

for ( int i = 0 ; i < visited.length ; i++ )
{
visited[i] = false;
}

for ( int i = 0 ; i < dist.length ; i++ )
{
dist[i] = Integer.MAX_VALUE;
}

dist[ s ] = 0;

for ( int i = 0; i < dist.length ; i++ )
{
final int next = minVertex ( dist, visited );
visited[ next ] = true;

final int [] n = wg.neighbors ( next );
for ( int j = 0 ; j < n.length ; j++ )
{
final int v = n[ j ];
final int d = dist[ next ] + wg.getWeight( next, v );
if ( dist[ v ] > d )
{
dist[ v ] = d;
pred[ v ] = next;
}
}
}
return pred;
}

private static int minVertex ( int [] dist, boolean [] v )
{
int x = Integer.MAX_VALUE;
int y = -1;   // graph not connected, or no unvisited vertices
for ( int i = 0 ; i < dist.length ; i++ )
{
if ( !v[i] && dist[i] < x )
{
y = i ;
x = dist[ i ];
}

}
return y;
}
```

For your reference here is the WeightedGraph class:

```public class WeightedGraph
{
private int [][]  paths;  // adjacency matrix
private Object [] places;

public WeightedGraph ( int n )
{
paths  = new int [ n ][ n ];
places = new Object[ n ];
}

public int size()
{
return places.length;
}

public void setLabel ( int vertex, Object label )
{
places[ vertex ] = label;
}

public Object getLabel ( int vertex )
{
return places[ vertex ];
}

public void addEdge ( int source, int target, int w )
{
paths[ source ][ target ] = w;
}

public boolean isEdge ( int source, int target )
{
return paths[ source ][ target ] > 0;
}

public void removeEdge ( int source, int target )
{
paths[ source ][ target ] = 0;
}

public int getWeight ( int source, int target )
{
return paths[ source ][ target ];
}

public int [] neighbors ( int vertex )
{
int count = 0;
for ( int i = 0 ; i < paths[vertex].length ; i++ )
{
if ( paths[vertex][i] > 0 )
{
count++;
}
}
final int [] answer = new int[ count ];
count = 0;
for ( int i=0 ; i < paths[ vertex ].length ; i++ )
{
if ( paths[ vertex ][ i ] > 0 )
{
}
}
}

public void print ()
{
for ( int j = 0 ; j < paths.length ; j++ )
{
for ( int i = 0 ; i < paths[ j ].length ; i++ )
{
if ( paths[ j ][ i ] > 0 )
{
System.out.println( places[ j ] + " to " + places[ i ] + " : " + paths[ j ][ i ] + " " );
}
}
}
}

/* This tests WeightedGraph and Dijkstra. Uncomment and  run to try them out and see that they are working fine.
public static void main (String args[])
{
final WeightedGraph t = new WeightedGraph (6);
t.setLabel (0, "first");
t.setLabel (1, "second");
t.setLabel (2, "third");
t.setLabel (3, "fourth");
t.setLabel (4, "fifth");
t.setLabel (5, "sixth");
t.print();

final int [] pred = Dijkstra.dijkstra (t, 0);
for (int n=0; n<6; n++) {
System.out.print(Dijkstra.printPath (t, pred, 0, n));
}
}
*/
}
```

The problem with this though is that it does not work for any source vertex other than 0... it always gives me an arrayindexoutofboundex error : -1 if I try to apply it to another source vertex. What should be added or modified here to allow for any source vertex...

Thanks in advance for all the help and/or direction!

This post has been edited by anoneemooz: 09 October 2010 - 08:26 PM

Is This A Good Question/Topic? 0

## Replies To: Dijkstra's Algorithm: Java Implementation Source Vertex Issues...

### #2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12297
• Posts: 45,396
• Joined: 27-December 08

## Re: Dijkstra's Algorithm: Java Implementation Source Vertex Issues...

Posted 09 October 2010 - 08:29 PM

Parallel arrays are not a good approach for this. I would suggest incorporating the dijsktra() method as part of the WeightedGraph class so you can directly access the Nodes use them to traverse the Graph in a similar fashion as Trees. It's much cleaner, much better encapsulated, and utilizes standard Graph theory.

### #3 anoneemooz

Reputation: 0
• Posts: 2
• Joined: 09-October 10

## Re: Dijkstra's Algorithm: Java Implementation Source Vertex Issues...

Posted 09 October 2010 - 08:37 PM

macosxnerd101, on 09 October 2010 - 07:29 PM, said:

Parallel arrays are not a good approach for this. I would suggest incorporating the dijsktra() method as part of the WeightedGraph class so you can directly access the Nodes use them to traverse the Graph in a similar fashion as Trees. It's much cleaner, much better encapsulated, and utilizes standard Graph theory.

Thanks for the advice but does that resolve the issue with the code as is? Is it the only way? I'm quite pressed for time since I have to incorporate these into a bigger project due soon and this has been a huge road block for me so I was looking for a way to just make minor edits within the codes as they are to get things working properly. I'll keep your advice in mind for future use though.