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
minHeap.add(source vertex)
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<PathWithV> minPQ = new MinPriorityQ<PathWithV>(new Comparator<PathWithV>() {
            @Override
            public int compare(PathWithV o1, PathWithV o2) {
                return o1.path - o2.path;
            }
        });
        PathWithV p = new PathWithV(sourceVertex, 0);
        minPQ.add(p);
        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 < targetVertexPath) {
                    distTo[edge.targetVertex] = distTo[vertex] + edge.weight;
                    edgeTo[edge.targetVertex] = vertex;
                    p = new PathWithV(edge.targetVertex, distTo[edge.targetVertex]);
                    minPQ.addOrUpdateKey(p);
                }
            }
        }
    }
}

Screenshot in ME-Mydoc
dijkstra