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 theminHeapminHeap.add(source vertex) while(!minHeap.isEmpty) { Vertex minVertex = minHeap.removeMin foreach edge incident to minVertex { if (the other vertex has shorter distance) { updatedistTo[edge.destVertex] updateminHeapof 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&lt;PathWithV&gt; minPQ = new MinPriorityQ&lt;PathWithV&gt;(new Comparator&lt;PathWithV&gt;() { @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 &lt; targetVertexPath) { distTo[edge.targetVertex] = distTo[vertex] + edge.weight; edgeTo[edge.targetVertex] = vertex; p = new PathWithV(edge.targetVertex, distTo[edge.targetVertex]); minPQ.addOrUpdateKey(p); } } } } }

## Leave a Reply