{"id":108473,"date":"2021-10-25T11:37:20","date_gmt":"2021-10-25T15:37:20","guid":{"rendered":"https:\/\/ibkrcampus.com\/?p=108473"},"modified":"2022-11-21T09:48:42","modified_gmt":"2022-11-21T14:48:42","slug":"dijkstra-algorithm-part-ii","status":"publish","type":"post","link":"https:\/\/www.interactivebrokers.com\/campus\/ibkr-quant-news\/dijkstra-algorithm-part-ii\/","title":{"rendered":"Dijkstra Algorithm \u2013 Part II"},"content":{"rendered":"\n

See Part I<\/a> for an overview of Dijkstra algorithm<\/em>.<\/p>\n\n\n\n

Pseudo code of Dijkstra algorithm<\/h2>\n\n\n\n

The pseudo code of Dijkstra algorithm is:<\/p>\n\n\n\n

function Dijkstra(L[1..n, 1..n]): matrix [2..n]\nmatrix D[2..n]\n{initialization}\nC <- {2, 3, \u2026, n} {S = N \\ C exists only implicitly}\nfor i \u2190 2 to n do D[i] \u2190 L[1, i]\n{greedy loop}\nrepeat n - 2 times\n\tv \u2190 some element of C that minimizes D[v]\n\tC \u2190 C \\ {v} {and implicitly S \u2190  S U {v}}\n\tfor each w \u2208 C do\n\t\tD[w] \u2190 min(D[w], D[v] + L[v, w])\nReturn D<\/code><\/pre>\n\n\n\n
Pseudo code.py <\/a>hosted with \u2764 by GitHub<\/a><\/code><\/pre>\n\n\n\n
Dijkstra algorithm table<\/h2>\n\n\n\n
Assume the following routed graph:<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
Dijkstra algorithm table<\/em><\/p>\n\n\n\n
Step<\/strong><\/td>v<\/strong><\/td>C<\/strong><\/td>D<\/strong><\/td><\/tr>
Initialization<\/td>–<\/td>{2, 3, 4, 5}<\/td>[50, 30, 100, 10]<\/td><\/tr>
1<\/td>5<\/td>{2, 3, 4}<\/td>[50, 30, 20, 10]<\/td><\/tr>
2<\/td>4<\/td>{2, 3}<\/td>[40, 30, 20, 10]<\/td><\/tr>
3<\/td>3<\/td>{2}<\/td>[35, 30, 20, 10]<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
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.<\/p>\n\n\n\n
Dijkstra algorithm time complexity<\/h2>\n\n\n\n
The initialisation requires a matrix L[1..n, 1..n] and therefore requires a time that is in the Order of n O(n)<\/p>\n\n\n\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)<\/p>\n\n\n\n
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)<\/p>\n\n\n\n
Therefore, the simple implementation of the Dijkstra algorithm requires a runtime that is O(n2)O(n2)<\/p>\n\n\n\n
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).<\/p>\n\n\n\n
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.<\/p>\n\n\n\n
See references for more information.<\/p>\n\n\n\n
\n\n\n\n
References<\/strong><\/p>\n\n\n\n