Setup

We are given a directed graph $G=(V,E)$ with a designated starting node $s$. Each edge $(u, v) \in E$ has a weight $w(u,v) \geq 0$ indicating its cost. For each vertex $v \in V$, it has a predecessor $v.\pi$ that is another vertex or NIL.

Goal

Find the shortest path from $s$ to every other vertex in the graph.

Pseudocode

$Q$ is a min-priority queue of vertices, keyed by their $d$ values.

1.DIJKSTRA (G, s)

S = $\varnothing$
Q = G.V
while $Q \neq \varnothing$
     u = EXTRACT-MIN(Q)
     S = S $\cup$ u
    for each vertex v $\in$ G.Adj[u]
        RELAX(u,v,w)

2.INITIALIZE-SINGLE-SOURCE (G,s)

for each vertex v $\in$ V[G]
     v.d = $\infty$
     $v.\pi$ = NIL
d[s] = 0

3. RELAX (u,v,w)

if v.d > u.d + w(u,v)
     v.d = u.d + w(u,v)
     v.$\pi$ = u

Proof of correctness

We want to show that the algorithm terminates with $u.d = \delta(s,u)$ for all $u \in V$, where $\delta(s,u)$ is the shortest path weight from $s$ to $u$, and is defined as \[ \delta(s, u) = \begin{cases} min\{w(p):s\xrightarrow{\text{p}}u\} , & \quad \text{if there is a path from s to u}\\\
\infty , & \quad \text{otherwise} \end{cases} \]

$w(p)$ is the sum of weights of the path $p$

We first show

At the start of each iteration of the while loop in Dijkstra’s algorithm, $v.d = \delta(s, v)$ for each vertex $v \in S$ (*)

1. Base Case:

$|S| = 0$, i.e when $S = \varnothing$, the statement is vacuously true.

2. Inductive Step:

Suppose the claim holds when $|S| = k$ for some $k \geq 1$. Now, let $S$’s size grow to $k+1$ by adding vertex $v$. We want to show $v.d = \delta(s,v)$.

If $v=s$ then $s.d = \delta(s,s) =0$. If $v \neq s$, it must be $S \neq \varnothing$. If there’s no path form $s$ to $v$, $v.d = \delta(s,v)= \infty$. If there are some path from $s$ to $v$, there sholud be one shortest path $p$ from $s$ to $v$.

Let us consider the first vertex $y$ on $p$ that is not in $S$, and let $x$ on $p$ be $y's$ predecessor. By induction hypothesis, $x.d = \delta(s,x)$. Because edge $(x, y)$ is relaxed in the previous iteration, by convergence property (if $s\rightarrow u\rightarrow v$ is a shortest path in G for some $u, v \in V$, and if $u.d = \delta(s,u)$ at any time prior to relaxing edge $(u,v)$, then $v.d = \delta(s,v)$ at all times afterwards), we have $y.d = \delta(s,y)$. Since $y$ is before $v$ on $p$ and all edge weights are nonnegative, we have $\delta (s,y) \leq \delta(s,v)$, and thus $y.d = \delta(s,y) \leq \delta(s,v) \leq v.d$

Because both vertices $v$ and $y$ are in $V-S$ when $v$ is selected by the algorithm, $v.d \leq y.d$. Thus, $y.d = \delta(s,y) = \delta(s,v) = v.d$, and so $v.d = \delta(s,v)$, and so complete the proof of (*).

Now

When the algorithm terminates, it means $Q = \varnothing$. Since the algorithm maintains the invariant that $Q = V - S$ (when initialization, $S = \varnothing$ and $Q$ contains all vertices of graph; for every time through while loop, a vertex is extracted from $Q$ and added to $S$, so the invariant is maintained), it means $S = V$, so $u.d = \delta(s,u)$ for all vertices $u \in V$

Time Complexity

Using priority queue implemented in min heap, the time to initialize the queue with setting all vertices' distances to $\infty$ is $O(V)$. Inside the while loop, we will do $V$ times EXTRACT_MIN operation, each of them will take $O(logV)$. Besides, we will do at most $E$ times of updating associated distance key for vertices in the queue, which will cost $O(ElogV)$. In total, the time will be $O((E+V)logV)$

Java implementation

In the code below, vertices is the hashmap containing the mapping between GeographicPoint and MapNode. MapNode is made up of GeographicPoint and list of MapEdge. MapNodes in vertices are converted to DiNode in hashmap diPoints by using the method convertMap to facilitate implementation of the algorithm. The constructPath method will return the path found by the algorithm from start to goal.

See the full framework of this project here (incomplete).

public List<GeographicPoint> dijkstra(GeographicPoint start,
    GeographicPoint goal, Consumer<GeographicPoint> nodeSearched){

    if(!vertices.containsKey(start) || !vertices.containsKey(goal)){
        System.out.println("input location does not exist in graph");
        return new LinkedList<GeographicPoint>();
    }

    HashMap<GeographicPoint, DiNode> diPoints = convertMap(vertices);
    HashMap<GeographicPoint, GeographicPoint> parentMap = new HashMap<>();
    Set<GeographicPoint> visitSet = new HashSet<>();
    PriorityQueue<DiNode> queue = new PriorityQueue<DiNode>();
    DiNode cur = diPoints.get(start);
    cur.sumDist = 0.0;
    queue.offer(cur);

    while(!queue.isEmpty()){
        cur = queue.poll();
        nodeSearched.accept(cur.mapNode.location);
        if(!visitSet.contains(cur.mapNode.location)){
            visitSet.add(cur.mapNode.location);
        }

        if(cur.mapNode.location.equals(goal)) {
            return constructPath(start, goal, parentMap);
        }

        for (MapEdge e : cur.mapNode.edges) {
            if(!visitSet.contains(e.end)){
                double nbSumDist = diPoints.get(e.end).sumDist;
                if(cur.sumDist + e.distance < nbSumDist){
                    // update cur as neightbor's parent in parent map
                    parentMap.put(e.end, cur.mapNode.location);
                    DiNode next = diPoints.get(e.end);
                    // update next neighbor's sum of distance
                    next.sumDist = cur.sumDist + e.distance;
                    // put neighbor with updated distance into priority queue
                    queue.offer(new DiNode(next.mapNode, next.sumDist));
                }
            }
        }

    }


    System.out.println("There is no such path");
    return new LinkedList<GeographicPoint>();
}

Above is one part of the back-end code of a project in UCSD’s Advanced Data Structure course. It utilizes the Google Map’s API, and can demonstrate route planning in a real world’s map as shown below. Note that the algorithm is a bit different from the one described above (instead of initializing the priority queue with inserting all vertices and later updating their sum of weighted distance, it enqueues the vertex after its distance is updated), but the general idea is the same.

Demo

References

[1] T. Cormen, C. Stein, R. Rivest, and C. Leiserson. Introduction to Algorithms (3rd ed.). MIT press,2009.
[2] J. Kleinberg and E. Tardos. Algorithm Design. Addison-Wesley, 2005
[3] https://www.coursera.org/learn/advanced-data-structures/home/week/4