// Dijkstra's algorithm with a priority queue (binary heap)
//
// Author: Rahul Simha
// Date: Oct, 2001.
import edu.gwu.algtest.*;
import edu.gwu.util.*;
import edu.gwu.debug.*;
import java.util.*;
import java.io.*;
/**
* Class Dijkstra
implements Dijkstra's algorithm
* with the customary priority queue, using a standard binary heap
* (with decreaseKey). The interface ShortestPathAlgorithm
* defines signatures of methods for single-source and all-pairs
* shortest-paths.
*
* @see ShortestPathAlgorithm
*/
public class Dijkstra implements ShortestPathAlgorithm {
// Debugging for internal use.
private static final boolean debug = true;
int algID; // Given by test-environment.
PropertyExtractor props; // Properties file.
int numVertices; // Number of vertices (when initialized).
boolean useMatrix; // Adjacency matrix or list?
double[][] adjMatrix; // The adjacency matrix (given as input).
GraphVertex[] adjList; // The adjacency list (given as input).
int[] predecessor; // Store predecessors to build MST.
double[] predecessorEdgeWeight; // Store edge weights as well.
GraphPath[][] paths; // paths[i][j] = shortest path from vertex
// i to vertex j. GraphPath is a list of edges.
//---------------- Algorithm interface ------------------------------------
public String getName ()
{
return "Dijkstra";
}
public void setPropertyExtractor (int algID, PropertyExtractor props)
{
this.algID = algID;
this.props = props;
}
//---------------- ShortestPathAlgorithm interface -----------------------
public void initialize (int numVertices)
{
this.numVertices = numVertices;
paths = new GraphPath [numVertices][];
for (int i=0; i < numVertices; i++)
paths[i] = new GraphPath [numVertices];
predecessor = new int [numVertices];
predecessorEdgeWeight = new double [numVertices];
}
public GraphPath[] singleSourceShortestPaths (double[][] adjMatrix, int source)
{
this.adjMatrix = adjMatrix;
// All the work is done here:
return singleSourceShortestPaths (source);
}
public GraphPath[] singleSourceShortestPaths (int source)
{
// Consistency check:
if (numVertices != adjMatrix.length) {
System.out.println ("ERROR: adjMatrix length not equal to numVertices");
return null;
}
// We are using an adjacency matrix.
useMatrix = true;
// Create heap. Note: BinaryHeap implements the PriorityQueueAlgorithm
// interface (that has insert, extractMin and decreaseKey operations.
PriorityQueueAlgorithm priorityQueue = new BinaryHeap (numVertices);
priorityQueue.initialize (numVertices);
// Since we are given an adjacency matrix, we need to build vertices
// to use in the priority queue. GraphVertex is a class that holds
// the vertex id and also can hold an edge-list (Therefore, it's
// used for the adjacency-list representation.
// NOTE: most importantly, GraphVertex implements the PriorityQueueNode
// interface that allows the priority queue to store indices inside the node.
GraphVertex[] vertices = new GraphVertex [numVertices];
for (int i=0; i 0) ) {
// We have found a neighbor: relax the edge (v,i).
double w = adjMatrix[v][i];
// If the current priority is higher, lower it via edge (v,i).
if (vertices[i].getKey() > v_key + w) {
// decreaseKey operation.
priorityQueue.decreaseKey (vertices[i], v_key+w);
// Record predecessor to build SPT later.
predecessor[i] = v;
}
}
} //endfor
}
// Next, we need to build the paths.
GraphPath path = null;
// path.edgeList[k] = k-th edge in path.
for (int i=0; i < numVertices; i++) {
if (i != source) {
// Find path from source to i and place that in paths[source][i]
// in reverse order (walking back from i).
// ... (not shown) ...
} // endif
} // endfor
return paths[source];
}
public GraphPath[][] allPairsShortestPaths (double[][] adjMatrix)
{
// We are using an adjacency matrix.
useMatrix = true;
this.adjMatrix = adjMatrix;
// Consistency check:
if (numVertices != adjMatrix.length) {
System.out.println ("ERROR: adjMatrix length=" + adjMatrix.length + " not equal to numVertices=" + numVertices);
return null;
}
// Now, compute shortest paths, one source at a time.
for (int source=0; source < numVertices; source++) {
singleSourceShortestPaths (source);
}
return paths;
}
public GraphPath[] singleSourceShortestPaths (GraphVertex[] adjList, int source)
{
// ... (not shown) ...
return null;
}
public GraphPath[][] allPairsShortestPaths (GraphVertex[] adjList)
{
// ... (not shown) ...
return paths;
}
public GraphPath[] singleSourceShortestPathsAdjList (int source)
{
// ... (not shown) ...
return paths;
}
public double getPathWeight (int source, int dest)
{
// ... (not shown) ...
return 0;
}
public GraphPath getPath (int source, int dest)
{
return paths[source][dest];
}
}