Dijkstra single source shortest algorithm in adjacency list form, which passes AOJ Single Source Shortest Path Problem is available @Github

The algorithm works like Prim algorithm of generating minimal spanning tree in that each round a vertex is added to the spanning tree. The rule of determining next vertex is minimal total weight from source vertex.

## Pseudo algorithm

• distTo[] is total weight of each vertex from source vertex.
• minHeap is a min binary heap keeping track of total weight of all vertices not in the spanning tree.
distTo[] initialized to INFINITE
create the minHeap
while(!minHeap.isEmpty) {
Vertex minVertex = minHeap.removeMin
foreach edge incident to minVertex {
if (the other vertex has shorter distance) {
update distTo[edge.destVertex]
update minHeap of edge.destVertex
}
}
}


## Technicalities

PriorityQueue in java.util is used as the binary heap but it lacks update(key, newValue) API. We wrap a PriorityQueue to mimic the bahavior by first removing the object if it is the queue and add to the queue again.

## Complexity Analysis

Time complexity of Dijkstra is O(E*log(V)) because at most E edges are iterated and at most V vertices in the binary heap.

## Core Java code

public static class DijkstraShortestPath {

Integer[] distTo; // index is vertex
Integer[] edgeTo;

public DijkstraShortestPath(WeightedDigraph graph, int sourceVertex) {
distTo = new Integer[graph.numVertex];
edgeTo = new Integer[graph.numVertex];

distTo[sourceVertex] = 0;
edgeTo[sourceVertex] = sourceVertex;
MinPriorityQ&amp;lt;PathWithV&amp;gt; minPQ = new MinPriorityQ&amp;lt;PathWithV&amp;gt;(new Comparator&amp;lt;PathWithV&amp;gt;() {
@Override
public int compare(PathWithV o1, PathWithV o2) {
return o1.path - o2.path;
}
});
PathWithV p = new PathWithV(sourceVertex, 0);
while (!minPQ.isEmpty()) {
int vertex = minPQ.remove().vertex;
for (WeightedDigraph.Edge edge : graph.srcEdges[vertex]) {
Integer targetVertexPath = distTo[edge.targetVertex];
if (targetVertexPath == null || distTo[vertex] + edge.weight &amp;lt; targetVertexPath) {
distTo[edge.targetVertex] = distTo[vertex] + edge.weight;
edgeTo[edge.targetVertex] = vertex;
p = new PathWithV(edge.targetVertex, distTo[edge.targetVertex]);