What are the applications of the shortest-path-algorithm?

Question

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.

Francisco

You could find your path to home with less bars, and avoid it. – Jeanette

Answer 1

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/

Imena

Answer 2

Given a number of cities with highways connecting them, find the shortest path from New York to Chicago.

The traffic and length of the highways are path weights.

Garland

This can also be used for various computer games. – Garland

Answer 3

Shortest path algorithms can be used to solve word ladder puzzles.

For example, change the word "cat" into the word "dog" by changing one letter at a time - "cat", "bat", "bag", "bog", "dog"

Millard

Answer 4

Shortest path problems form the foundation of an entire class of optimization problems that can be solved by a technique called column generation. Examples include vehicle routing problem, survivable network design problem, amongst others. In such problems there is a master problem (usually a linear program) in which each column represents a path (think of a path in a vehicle routing problem as one candidate route that a vehicle can take, think of a path in a network design problem as a possible route over which a commodity can be sent between a source and a destination). The master problem is repeatedly solved. Each time, using the metrics of the solution, a separate problem (called the column-generation subproblem) is solved. This problem turns out to be a shortest path problem (usually with side constraints or negative arc lengths rendering the problem NP-Hard). If a new useful path is obtained, it is added to the original master problem which is now re-solved over a larger subset of paths leading to increasingly better (lower cost, usually) solutions.

Mckay

Answer 5

Given a network of computers (eg, a peer-to-peer application), find the shortest path from machine A to machine B.

Garland

SLaks, but why would you need a shortest path in a peer-to-peer application? – Ebby

In a peer-to-peer application, the two machines are not necessarily connected using a single connection. All connections go through an initial gateway and then through many inbetween routers or switches, essentially forming a network. This is where the shortest path algo comes. – Blanca

Answer 6

In video games, these algorithms are frequently used to find the shortest path between two points on a map. "Pathfinding," as it is called in this context, can be used by AI to plot routes, or by the game engine to assist users in plotting routes.

Bellows

Answer 7

One example that I can see it probably being used is in pre-setted points devices that need to travel through certain points with a specific amount of battery charge or fuel.

In the military we have certain small unmanned aerial vehicles/devices which has some pre-setted point it needs to scout, and since it must travel really far distances, on a small device like that it would be too expensive to try to control it via satellite, and radio control would deteriorate before reaching the farthest point. That is where the algorithm comes into play.

Simply set up some point you want the thing to scout and release it. Letting it find the shortest path traveled to cover all points. It doesn't require major tools, hence it is more affordable and portable.

Pomp

Answer 8

Social Network... finding the shortest path between two persons (degree of separation)

Huron

This sounds really interesting! But what could this be used to? – Fennel

You know in linkedIn, they provide that some person is your 2nd Connection or 3rd Connection, there 2 is the shortest path from you to that person. – Huron

Shown that each people in America are related to each other with 6 relation:) – Cullan

Answer 9

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

Heterotopia

Answer 10

Grieg

ts is an sp class problem though – Grieg

What's an "sp class problem"? – Freddyfredek

Traveling Salesman is a set of shortest paths problem - sorry was on a phone – Grieg

Answer 11

The shortest path is often used in SNA (Social Network Analysis) to calculate betweenness centrality among others. Usually people with the strongest bonds tend to communicate through the shortest path. Knowing in a graph the shortest path between people (nodes) can let you know hidden strong bonds. You can discover many interesting things in a graph by just calculating some metrics.

Schatz