# Notes on Dijkstra's Algorithm

### 2017-07-24

**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

foreach vertex v`$\in$`

G.Adj[u]

RELAX(u,v,w)

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

foreach vertex v`$\in$`

V[G]

v.d =`$\infty$`

`$v.\pi$`

= NIL

d[s] = 0

- RELAX (u,v,w)

ifv.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$`

(*)

- Base Case:

`$|S| = 0$`

, i.e when `$S = \varnothing$`

, the statement is vacuously true.

- 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 throughwhileloop, 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