Dijkstra’s Shortest Path Algorithm

Theory of Computation


The shortest path between u and v is denoted $\delta(u,v)$, if there is no path, then $\delta(u,v)=\infty$

Can a shortest path contain a cycle?

A directed cycle is:

  • Positive: if its edge weights sum up to a positive number

  • Negative: if its edge weights sum up to a negative number

If there is a positive cycle in the graph, it will not be contained in any shortest path between u and v so we can assume that the shortest paths we find contain no positive cycles.

However if there is a negative cycle between u and v, then $\delta(u,v)=-\infty$ so we shall assume that the graphs we consider do not contain negative cycles.

Single-Source Shortest Paths

  • Aim: to describe an algorithm that solves the single-source shortest paths problem, i.e. an algorithm that finds the shortest path from a specific source vertex

  • This is a generalization of BFS

  • So the output of the algorithm should be two arrays d, $\pi$ where for each vertex v:

    • $d(v)=\delta(s,v)$

    • $\pi(v)$ is the predecessor of v

Relaxation

  • Assume that the weight on every edge is non-negative

  • We do not directly compute the entry $d(v)=\delta(s,v)$

  • Instead, at every step, $d(v)$ is an estimate for $\delta(s,v)$

    • Initially, $d(v)=\infty$, and it always remains $d(v)\geqslant \delta(s,v)$

    • $d(v)$ is updated (i.e. it decreases) as shorter paths are found

    • At the end of the algorithm we have $d(v)=\delta(s,v)$

Initialise-Single-Source(G,s)

for each vertex v in V(g):
    d(v)=infinity
    pi(v)=NULL
d(s)=0

The process of relaxing an edge (u,v):

  • Test whether we can improve the shortest path from s to v that we found so far, by going through u

  • If yes, then update $d(v)$ and $\pi(v)$

    • Decrease the estimate $d(v)$

    • Update the predecessor $\pi(v)$ to u

  • The algorithm first calls initialise-single-source and then it repeatedly relaxes the appropriate edges (according to the weight function w)

Relax(u,v,w)

if d(v)>d(u)+w(u,v):
    d(v)=d(u)+w(u,v)
    pi(v)=u

Dijkstra’s Algorithm

  • Initialisation: distance to source A is 0, $S=\varnothing$, Q=V

  • S stores the vertices v for which we already found $\delta(A,v)$

  • Q stores all the other vertices

  • While q is not empty

    • Remove from Q the vertex u for which d(u) is minimum

    • Add this vertex to s

    • Relax all edges leaving u

Dijkstra({G,w,s})

Initialise-Single-Source(G,s)
S=[]
Q=V(G)
while Q!=[] do
    u=Extract-Min(Q)
    S=S+{u}
    for each vertex v in Adj(u) do
        Relax(u,v,w)

Runtime

Initialisation is done in $\mathcal{O}(V)$ time - two operations per vertex

Finding the vertex v in Q with minimum d(v) takes $\mathcal{O}(V)$ time and this is done v times

  • To find the minimum, just scan the set Q

  • To compute the new vertex in S, find the new minimum of Q

Relaxation takes in total $\mathcal{O}(E)$ time as every edge is relaxed once

The total running time is $\mathcal{O}(V+V^2+E)=\mathcal{O}(V^2)$

However using a more sophisticated implementation for extracting the minimum for Q it can run in $\mathcal{O}(V\log V+E)$ time

Properties of shortest paths and relaxation

Triangle Inequality

For all edges (u,v) we have $\delta(s,v)\leqslant \delta(s,u)+w(u,v)$

Optimal substructure
Any subpath of a shortest path is also a shortest path
Upper bound property

For every vertex v, we have $d(v)\geqslant \delta(s,v)$

No-path property

If $\delta(s,v)=\infty$ then we have $d(v)=\infty$ at every iteration

Convergence property

If there is a shortest path from s to v including the edge (u,v) and if $d(u)=\delta(s,u)$, then we obtain $d(v)=\delta(s,v)$ when $(u,v)$ is relaxed

Correctness of Dijkstra’s algorithm

We need to prove the loop invariant always remains true.

At the start of each iteration of the while loop, $d(v)=\delta(s,v)$ for every $v\in S$

  • Initialisation: at the start of the algorithm S is empty, so the loop invariant is trivially true

  • Maintenance: we need to show that $d(u)=\delta(s,u)$ when u is added to S

  • Termination: at the end, S contains every vertex, which implies that $d(v)=\delta(s,v)$ for all vertices v in the graph