Menu
The shortest path between nodes in a graph can be found by several algorithms (Dikstra, A-star, etc).
But what applications does this problem have? (I know quite a few already, but I would like to see many more examples).
Please give only one application/answer! Explain the application, and how it can be transformed to a shortest-path problem.
444
Dijkstra's algorithm is widely used in the routing protocols required by the routers to update their forwarding table. The algorithm provides the shortest cost path from the source router to other routers in the network.
Many benefits can be obtained when knowing the shortest or fastest route in a travel route, as an example, can save travel time, power, less fuel consumption, and the density of vehicles on certain segments can decompose.
Applications for shortest paths As we saw above, transporation problems (with solutions like Google Maps, Waze, and countless others) are a prime example of real-world applications for shortest path problems.
The shortest-path algorithm calculates the shortest path from a start node to each node of a connected graph. Developed in 1956 by Edsger W. Dijsktra, it is the basis for all the apps that show you a shortest route from one place to another.
A cool application that hasn't been mentioned is in edge detection and segmentation. See Interactive Segmentation with Intelligent Scissors. You may know this as "magnetic lasso" in Photoshop
195
There is an interesting, not directly obvious, application of the shortest path algorithms that is probably used quite often in algorithmic trading and financial sector that deals with trading assets and goods.
Imagine that you could convert 1000 USD to 950 EUR and then 950 EUR to 1020 CAD which you convert back to 1007 USD :) Just by converting from currency to currency you can make money.
This situation is called arbitrage opportunity. This can be done with any asset and between different markets.
In this case, the relations between assets are modeled as directed edge-weighted graph and finding so called negative-cycles in the graph is in fact finding these arbitrage opportunities.
You can see more details with nice explanation and examples here: http://algs4.cs.princeton.edu/44sp/
31
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
