This website uses cookies to collect usage information in order to offer a better browsing experience. By browsing this site or by clicking on the "ACCEPT COOKIES" button you accept our Cookie Policy.

Dijkstra Algorithm – Part III

QuantInsti

Contributor:
QuantInsti
Visit: QuantInsti

See Part I for an overview of Dijkstra algorithm and Part II for pseudo code of Dijkstra algorithm.

When to use the Dijkstra algorithm?

As we have seen, the Dijkstra Algorithm is used to solve the problem of minimum paths in a directed graph. The implementation we have been analysing always gives us the optimal matrix of minimum paths.

Typical applications of the Dijkstra algorithm:

  • Robot navigation.
  • Typesetting in TeX.
  • Urban traffic planning.
  • Tramp steamer problem.
  • Optimal pipelining of VLSI chip.
  • Telemarketer operator scheduling.
  • Subroutine in higher level algorithms.
  • Routing of telecommunications messages.
  • Approximating piecewise linear functions.
  • Exploiting arbitrage opportunities in currency exchange.
  • Open Shortest Path First (OSPF) routing protocol for IP.
  • Optimal truck routing through a given traffic congestion pattern.

Graphs

GraphVerticesEdges
FinancialStocks, currencyTransactions
Neural networksNeuronsSynapses
SchedulingTasksPrecedence constraints
CommunicationTelephones, computersFibre optic cables
CircuitsGates, registers, processorsWires
MechanicalJointsRods, beams, springs
HydraulicReservoirs, pumping stationsPipelines
GamesBoard positionsLegal moves
InternetWeb pagesHyperlinks

Dijkstra algorithm vs Kruskal algorithm

Dijkstra algorithm and Kruskal algorithm – both these algorithms belong to the family of greedy algorithms. Although Dijkstra algorithm is used to solve the shortest path problem, the Kruskal algorithm is used to solve the minimum covering graph.


Dijkstra algorithm vs Prim algorithm

Dijkstra algorithm and Prim algorithm – both algorithms belong to the family of greedy algorithms. Although the Dijkstra algorithm is used to solve the shortest path problem, the Prim algorithm is used to solve the minimum covering graph as the Kruskal algorithm.


Prim algorithm vs Kruskal algorithm

What is the difference between Prim algorithm and Kruskal algorithm? The difference is in the way the greedy algorithm is implemented. While the Kruskal algorithm always chooses the edges in increasing order of length and forms disjoint subsets to finally find the optimal solution, the Prim algorithm always has the optimal set at a given time.

Stay tuned for the next installment in which Mario Pisa will demonstrate how to find the shortest path using the Dijkstra algorithm.

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.

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.

trading top