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.
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 Traders’ Insight that is provided by third-parties and not by Interactive Brokers does NOT constitute a recommendation by Interactive Brokers that you should contract for the services of that third party. Third-party participants who contribute to IBKR Traders’ Insight 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 permission from QuantInsti. The views expressed in this material are solely those of the author and/or QuantInsti and IBKR 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 sell or the solicitation of an offer to buy any security. To the extent that this material discusses general market activity, industry or sector trends or other broad based economic or political conditions, it should not be construed as research or investment advice. To the extent that it includes references to specific securities, commodities, currencies, or other instruments, those references do not constitute a recommendation to buy, sell or hold such security. 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.
In accordance with EU regulation: The statements in this document shall not be considered as an objective or independent explanation of the matters. Please note that this document (a) has not been prepared in accordance with legal requirements designed to promote the independence of investment research, and (b) is not subject to any prohibition on dealing ahead of the dissemination or publication of investment research.
Any trading symbols displayed are for illustrative purposes only and are not intended to portray recommendations.
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.