Thread: Dijstra's Algorithm Problems

Hey guys, So I'm trying write a dijstra's implementation in java. First off, here is the algorith:

package lab3;
 
import java.util.HashMap;
import java.util.Stack;
 
/**
 * Compute shortest paths in a graph.
 *
 * Your constructor should compute the actual shortest paths and
 * maintain all the information needed to reconstruct them.  The
 * returnPath() function should use this information to return the
 * appropriate path of edge ID's from the start to the given end.
 *
 * Note that the start and end ID's should be mapped to vertices using
 * the graph's get() function.
 */
class ShortestPaths {
 
	Multigraph graph;
	final int INF = Integer.MAX_VALUE;
	PriorityQueue<Integer> Q;
	int n;
	int dist[];
	Handle handles[];
	Edge edge[];
 
	/**
	 * Constructor
	 */
	public ShortestPaths(Multigraph G, int startId) {
		Q = new PriorityQueue<Integer>();
		graph = G;
		n = graph.nVertices();
		dist = new int [n];
		edge = new Edge [n];
		handles = new Handle[n];
 
		for (int i = 0; i<n; i++){
			dist[i] = INF;
		}
		dist[startId] = 0;
 
		Handle h = Q.insert(startId, dist[startId]);
		handles[startId] = h;	
		Q = new PriorityQueue<Integer>();
		while (!Q.isEmpty()){
			Vertex v = graph.get(Q.min());
			Q.extractMin();
			while (v.adj().hasNext()){
				relax(v.adj().next());	
			}		
		}	
	}
 
	private void relax(Edge e) {
		Handle h;
		int v = e.from().id();
		int w = e.to().id();
		if (dist[w] > dist[v] + e.weight()) {
			dist[w] = dist[v] + e.weight();
			edge[w] = e;
			if (handles[w].getIndex() != -1){
				Q.decreaseKey(handles[w], dist[w]);
			}
			else{
				h = Q.insert(w, dist[w]);
				handles[w] = h;
			}
		}
	}
 
	/**
	 * Calculates the list of edge ID's forming a shortest path from the start
	 * vertex to the specified end vertex.
	 *
	 * @return the array
	 */
	public int[] returnPath(int endId) {
		int c = 0;
		int[] path = new int[edge.length];
		for (Edge e = edge[endId]; e != null; e = edge[e.from().id()]) {
			path[c] = e.id();
			c++;
		}
		return path;
	}
 
 
}

I followed someone else's psuedocode very closely but for whatever reason, my edge[] array is just full of null data, which means I can't actually return the shortest path. Any ideas on why that's happening/how to fix it? Maybe I'm not understanding dijstra's correctly. Anyway, thanks for your help.

Hey guys, So I'm trying write a dijstra's implementation in java. First off, here is the algorithm:

package lab3;
 
import java.util.HashMap;
import java.util.Stack;
 
/**
 * Compute shortest paths in a graph.
 *
 * Your constructor should compute the actual shortest paths and
 * maintain all the information needed to reconstruct them.  The
 * returnPath() function should use this information to return the
 * appropriate path of edge ID's from the start to the given end.
 *
 * Note that the start and end ID's should be mapped to vertices using
 * the graph's get() function.
 */
class ShortestPaths {
 
	Multigraph graph;
	final int INF = Integer.MAX_VALUE;
	PriorityQueue<Integer> Q;
	int n;
	int dist[];
	Handle handles[];
	Edge edge[];
 
	/**
	 * Constructor
	 */
	public ShortestPaths(Multigraph G, int startId) {
		Q = new PriorityQueue<Integer>();
		graph = G;
		n = graph.nVertices();
		dist = new int [n];
		edge = new Edge [n];
		handles = new Handle[n];
 
		for (int i = 0; i<n; i++){
			dist[i] = INF;
		}
		dist[startId] = 0;
 
		Handle h = Q.insert(startId, dist[startId]);
		handles[startId] = h;	
		Q = new PriorityQueue<Integer>();
		while (!Q.isEmpty()){
			Vertex v = graph.get(Q.min());
			Q.extractMin();
			while (v.adj().hasNext()){
				relax(v.adj().next());	
			}		
		}	
	}
 
	private void relax(Edge e) {
		Handle h;
		int v = e.from().id();
		int w = e.to().id();
		if (dist[w] > dist[v] + e.weight()) {
			dist[w] = dist[v] + e.weight();
			edge[w] = e;
			if (handles[w].getIndex() != -1){
				Q.decreaseKey(handles[w], dist[w]);
			}
			else{
				h = Q.insert(w, dist[w]);
				handles[w] = h;
			}
		}
	}
 
	/**
	 * Calculates the list of edge ID's forming a shortest path from the start
	 * vertex to the specified end vertex.
	 *
	 * @return the array
	 */
	public int[] returnPath(int endId) {
		int c = 0;
		int[] path = new int[edge.length];
		for (Edge e = edge[endId]; e != null; e = edge[e.from().id()]) {
			path[c] = e.id();
			c++;
		}
		return path;
	}
 
 
}

I followed someone else's psuedocode very closely but for whatever reason, my edge[] array is just full of null data, which means I can't actually return the shortest path. Any ideas on why that's happening/how to fix it? Maybe I'm not understanding dijstra's correctly. Anyway, thanks for your help.