Non-literal applications of "Shortest Path" algorithm?

Question

It's obvious that it's used in stuff like Google Maps, but what are some more metaphorical applications where you're minimizing the path between nodes (which can represent anything)

Answer 1

I'm not sure this is "non-obvious", but you can use a shortest path algorithm to numerically solve calculus of variations boundary value problems (i.e. where you know the starting and ending values). This can be done, for example, by creating a 2D grid of points, for example:

The integral you want to minimize is a path integral which takes the form:

$$ S = \int g(f, \dot{f}, t)dt $$

You can approximate this integral using edges that connect two grid points. The weight of the edge is the approximate value of this piece of the integral. That is, you estimate the $\dot{f} \approx \frac{\Delta f}{\Delta t}$, then plug into $g$ and approximate the integral as $\int_t^{t + \Delta t} gdt \approx g\Delta t$. You have to introduce a lot of extra nodes to create edges in many different directions (from each node) to accurately solve the problem. Once you have the graph setup (the nodes and edges with their edge weight), you simply solve the shortest path problem to find the solution from a starting node to an end node (or you could do an all-pairs shortest path algorithm to find a more general solution).

Here's an actual example of using this to find an optimum path to take between two polygonal lines using something very similar to dynamic time warping (this actually is an invariant DTW scheme). The first solution requires monotonicity and the second doesn't. If you don't know anything about free space diagrams, the white regions represent points (from both lines) that are less than a certain distance from each other. You can see that the non-monotonic solution sort of tends towards the middle of the free space:

If you want more information, you can read Curve Matching, Time Warping, and Light Fields: New Algorithms for Computing Similarity between Curves (it's a PDF). They explain all of this in more detail (and present a translation invariant measure).

Caveat

It's worth pointing out that this algorithm fails for some problems. Specifically, it fails for problems where the solution is a sinusoid. If you try to apply this problem to a harmonic problem (specifically one where the solution should be a sinusoid) it fails miserably. Now part of this is that periodic solutions are not that amenable to boundary value problems. The problem with those is that the boundaries often can result in many different solutions.

Answer 2

Th line-breaking algorithm in TeX works by considering a graph with each potential line break in a paragraph as a node and an edge between two nodes if there's an appropriate amount of text (and glue, etc.) between them to fill a line, weighted by an aesthetic "demerit" score for the potential line.

For each paragraph TeX will then compute the path from an implicit break point at the beginning to a break point at the end of the paragraph that incurs a minimal total amount of "demerits".

Answer 3

I once implemented a printer driver that would accept different formats of input. The printer itself was a Hewlett-Packard and required input in their proprietary “PCL” format. The printer driver had a configuration file that contained lines like this one:

   png -> pnm   0.8   pngtopnm %I > %O

This meant that an input in png format could be turned into a pnm format input by using the command pngtopnm %I > %O, and such a conversion has a quality score of 0.8.

The printer driver viewed this as an edge with length 0.8 in a directed graph. Given an input in any format it would then compute the shortest path to the pcl node, apply the appropriate commands to convert the input to PCL format, and send the result to the printer.

Answer 4

This is a specific instance of JackofAll's answer above: I've seen it used in a data dictionary context, where data models have a version number: it was used to find the shortest path from version x to version y, so that an automatic script could be generated to bundle up the data model changes to move a datamodel at version x to version y.

Answer 5

We can somewhat simplified describe a racing car's position on track as a 2D coordinate set, a facing and a speed. These combine to a 4D vector.

Given some finite resolution for each parameter we can describe all of the car's possible routes as a directed graph between such 4D vectors where each node point towards the nodes that are reachable depending on driver input.

The shortest route on this graph is the fastest route on track.

For practical use you'd probably want to include more variables in the position in order to describe physics more accurately, and then you would need to apply some heavy optimisation in order to get a graph that is small enough to work with.

It doesn't automatically solve the problem, but I think it is still beneficial to consider the fastest racing line problem to be just another shortest route problem that happen to take place in a vector space of assorted properties.

Answer 6

ISOMAP algorithm relates a collection of observations in a high-dimensional space to a lower-dimensional equivalent, thus performing dimension reduction. The algorithm calculates the "low-dimensional embedding" using a graph that connects the closest neighbors with a link, and the distance between all other points is calculated using a shortest path on that graph.

For details, see http://isomap.stanford.edu/