Minimum Paths

Suppose we have a graph as shown below.

When we are calculating paths, we simply choose our traversal points and add up the weights.

For example, we compute all of the paths which move us from \(A\) back to itself.

\[A \rightarrow B \rightarrow C \rightarrow E \rightarrow A = 0.5 + 1.2 + 1.1 + 0.5 = 3.3 \] \[A \rightarrow B \rightarrow D \rightarrow A = 0.5 + 0.8 + 0.9 = 2.2 \] \[A \rightarrow B \rightarrow D \rightarrow E \rightarrow A = 0.5 + 0.8 + 0.3 + 0.5 = 2.1 \]

We may have intuitively thought that \(A\) to \(B\) to \(D\) to \(A\) was the shorter path since it contains fewer nodes, but infact \(A\) to \(B\) to \(D\) to \(E\) to \(A\) is the shortest path with a total value of \(2.1\) compared to \(2.2\).

Applications

A concrete application is in the traffic direction software in GoogleMaps or Waze.

While I'm not sure of how each of these specific apps have been implemented, the way that I would implement something similar would be to first create a representation of the terrain, specifically roadways. We would keep it pretty simple, roads are edges, and where ever a road happens to split or crosses with another road is a node. The next thing we would need to do is determine the weights of each individual edge.

At first, I imagine that these apps simply computed weights with a formula which would incorporate distances between nodes and possibly roadway designations, meaning certain main roads, thoroughfares, and roads through business districts will naturally be more busy during certain periods of the day while residential roads, country roads, and so forth, will have less activity. However, over time, as people are regularly using the app, they can collect massive amounts of data such as the average vehicle speed during various time periods between nodes. The formula therefore becomes more complex, but can then utilize Bayesian inference and other statistical tools to iterativelly improve the edge weights.

Once we have a proper cyclical, weight, digraph, then determining shortest paths and similar is as simple as applying well known algorithms for computing minimum spanning trees, Dijkstra's algorithm, etc.