See the previous installments in this series to learn more about Dijkstra Algorithm. Part I offers an overview of Dijkstra algorithm and Part II provides pseudo code of Dijkstra algorithm. Part III demonstrates a comparison with other algorithms and Part IV presents the shortest path using the Dijkstra algorithm.
Why does the Dijkstra algorithm fail for negative weights?
Dijkstra algorithm doesn’t work for graphs with negative distances. Negative distances can lead to infinite cycles that must be handled by specialized algorithms such as Bellman-Ford’s algorithm or Johnson’s algorithm.
For us who are trying to do quantitative trading, this is not a minor problem, but quite the opposite. It is a big problem if we want to use this technique for trading.
One of the applications we have of Dijkstra algorithm is currency arbitrage, where each node is a currency and each vertex addresses, telling us the exchange rate. We can therefore construct a graph for this scenario.
Conclusion
As we have seen, the Dijkstra algorithm finds the optimal solution to obtain the shortest path in a graph from an origin to the rest of its nodes.
This algorithm has application in countless problems that can be represented as a graph or tree.
It differs from the Kruskal algorithm and Prim algorithm in that they focus on discovering the minimum coverage tree, i.e., how to cover the entire graph efficiently, while the Dijkstra algorithm focuses on optimizing the shortest path where it is not necessary to cover all the edges of the graph, but to reach all the nodes.
Finally, we have seen that the Dijkstra algorithm has problems such as negative weights for the edges, for which the Bellman-Ford or Johnson algorithms are used.
Dig into the world of algorithms and trading, start your quest to upgrade your knowledge of Algorithmic Trading with the Executive Programme in Algorithmic Trading (EPAT) – a comprehensive course covering topics ranging from Statistics & Econometrics to Financial Computing & Technology including Machine Learning and more. Check it out here.
Visit QuantInsti for additional insight on this topic: https://blog.quantinsti.com/dijkstra-algorithm/
Disclosure: Interactive Brokers
Information posted on IBKR Campus that is provided by third-parties does NOT constitute a recommendation that you should contract for the services of that third party. Third-party participants who contribute to IBKR Campus are independent of Interactive Brokers and Interactive Brokers does not make any representations or warranties concerning the services offered, their past or future performance, or the accuracy of the information provided by the third party. Past performance is no guarantee of future results.
This material is from QuantInsti and is being posted with its permission. The views expressed in this material are solely those of the author and/or QuantInsti and Interactive Brokers is not endorsing or recommending any investment or trading discussed in the material. This material is not and should not be construed as an offer to buy or sell any security. It should not be construed as research or investment advice or a recommendation to buy, sell or hold any security or commodity. This material does not and is not intended to take into account the particular financial conditions, investment objectives or requirements of individual customers. Before acting on this material, you should consider whether it is suitable for your particular circumstances and, as necessary, seek professional advice.
Disclosure: Forex
There is a substantial risk of loss in foreign exchange trading. The settlement date of foreign exchange trades can vary due to time zone differences and bank holidays. When trading across foreign exchange markets, this may necessitate borrowing funds to settle foreign exchange trades. The interest rate on borrowed funds must be considered when computing the cost of trades across multiple markets.