Dijkstra's algorithm for shortest distances and routes

Dijkstra's algorithm

Dijkstra's algorithm builds shortest distances from one source in a weighted graph with positive edge weights. Add each edge weight to the permanent distance already reached, retain the smaller label and make the globally smallest temporary label permanent

1. Start at the source Give the source a distance label of zero before relaxing any edges \(\displaystyle d(S)=0\)
2. Use cumulative labels Add an edge weight to the distance label at the permanent vertex \(\displaystyle d(P)=4,\;w(PQ)=3\;\Rightarrow\;4+3=7\)
3. Retain the smaller value Compare a proposed label with the existing temporary label \(\displaystyle \min\{9,7\}=7\)
4. Choose the global minimum Make the temporary vertex with the smallest label permanent next \(\displaystyle d(B)=5<d(C)=8\;\Rightarrow\;B\text{ becomes permanent}\)

Worked example

A weighted road network has the edges and weights shown below. Apply Dijkstra's algorithm from S to find the shortest distance to R and recover a route

1. \(\displaystyle d(S)=0,\quad d(P)=0+4=4,\quad d(Q)=0+10=10\)Set the source label to 0 and relax the two edges leaving S.
2. \(\displaystyle 4<10\;\Rightarrow\;P\text{ is next},\quad d(T)=4+3=7\)P has the smaller temporary label, so relax the edge from P to T.
3. \(\displaystyle 7<10,\quad d(Q)=\min\{10,7+2\}=9,\quad d(R)=7+5=12\)T is next, and its relaxations improve Q and label R.
4. \(\displaystyle d(Q)=9<d(R)=12,\quad 9+6=15>12\;\Rightarrow\;d(R)=12\)Make Q permanent and check its edge to R; R keeps its smaller label of 12
5. \(\displaystyle 0+4=4,\quad 4+3=7,\quad 7+5=12\;\Rightarrow\;S\!-!P\!-!T\!-!R,\quad 4+3+5=12\text{ km}\)Exact predecessor differences recover the route S to P to T to R, with total distance 12 km

Common mistakes

Difficulty levels

Questions about this topic

In this chapter