Dijkstra Algorithm – Part II

See Part I for an overview of Dijkstra algorithm.

Pseudo code of Dijkstra algorithm

The pseudo code of Dijkstra algorithm is:

function Dijkstra(L[1..n, 1..n]): matrix [2..n]
matrix D[2..n]
{initialization}
C <- {2, 3, …, n} {S = N \ C exists only implicitly}
for i ← 2 to n do D[i] ← L[1, i]
{greedy loop}
repeat n - 2 times
	v ← some element of C that minimizes D[v]
	C ← C \ {v} {and implicitly S ←  S U {v}}
	for each w ∈ C do
		D[w] ← min(D[w], D[v] + L[v, w])
Return D

Pseudo code.py hosted with ❤ by GitHub

Dijkstra algorithm table

Assume the following routed graph:

Dijkstra algorithm table

Step	v	C	D
Initialization	–	{2, 3, 4, 5}	[50, 30, 100, 10]
1	5	{2, 3, 4}	[50, 30, 20, 10]
2	4	{2, 3}	[40, 30, 20, 10]
3	3	{2}	[35, 30, 20, 10]

Obviously the matrix D would not change if we did one more interaction to remove the last element of C {2} and for this reason the main loop only repeats n-2 times.

Dijkstra algorithm time complexity

The initialisation requires a matrix L[1..n, 1..n] and therefore requires a time that is in the Order of n O(n)

The repeat loop requires looping through all the elements of C, so the total time is in the order of n2.O(n2)n2.O(n2)

The loop for each requires looping through all the elements of C, so the total time is on the order of n2.O(n2)n2.O(n2)

Therefore, the simple implementation of the Dijkstra algorithm requires a runtime that is O(n2)O(n2)

Depending on the implementation of the algorithm and as long as the number of edges is much smaller than n2n2, we can improve the complexity up to O((a + n) log n) if the graph is connected and is in O(a log n), but if the graph is dense we can only reach O(n2/logn).O(n2/logn).

To improve Dijkstra’s simple algorithm, one can make an implementation of k-ary heaps as proposed by Johnson. Fredman and Tarjan further improve the complexity by using a Fibonacci heap.

See references for more information.

---

References

• Fundamentals of algorithmics by G. Brassard and P. Bratley
• Princeton University, Dijkstra’s algorithm and Bellman-Ford algorithm
• scipy.sparse.csgraph.dijkstra library
• Arbitrage Strategy using Negative Cycle Detection Algorithm
• Currency aribitrage detection

Stay tuned for the next installment in which Mario Pisa will discuss use the Dijkstra algorithm.

Visit QuantInsti for additional insight on this topic: https://blog.quantinsti.com/dijkstra-algorithm/