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 ) { answer[ count++ ] = i; } } return answer; } 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.addEdge (0,1,2); t.addEdge (0,5,9); t.addEdge (1,2,8); t.addEdge (1,3,15); t.addEdge (1,5,6); t.addEdge (2,3,1); t.addEdge (4,3,3); t.addEdge (4,2,7); t.addEdge (5,4,3); 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