What are the applications of the shortest-path-algorithm?
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.
Answer
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/