Shortest Path

In a Geo-spatial Network application, it is a common feature to compute shortest paths for various purposes, e.g. planning a route from current location to a destination on the geographic map; scheduling nearest Uber cars to users requesting ride service.

Specifically, there are two types of tasks to compute shortest paths: single-source and multi-source, both of which are computed based on weighted graph structures. One of the most important algorithms in the 20th is Dijkstra's Algorithm.

Generality

a path from 𝓋0 -> 𝓋k is defined by p (𝓋0 -> 𝓋0 is 0), and the shortest path from source 𝓊 to 𝓋 is:

Figure 1. A Delta Function Denotes the Shortest Path Total Value

Single-Source

Given weighted graph G = (V, E), weight w(u, v) of two vertices (u, v) and a source S, compute δ(S, vi) wherein vi is a vertex from vertices set V.

Figure 2. Auxiliary Static Data Structure to Store Shortest Paths

Mathematically, use the above structure to initialize to infinity and converge to the shortest paths values from a given source S would yield the final solution at hand.

In addition, define another array πi (i=1,2,...,n) to track the predecessor of all vertices, where π[s] = s in order to output the shortest paths.

Note: the convergence step is formally termed as Relaxation, which would be covered in Dijkstra's Algorithm discussion.

The classical Dijkstra's Algorithm and Bellman-Ford algorithm are further discussed based on the above assumptions.

Dijkstra's Algorithm

Invented by Turing Award winner Edsger W. Dijkstra, this algorithm adopts a greedy approach to search for the shortest path among all the paths leading from a single source to the destination.

Fundamental Ideas

It is applicable for both directed and undirected graphs, in which the edges must have non-negative weights. In the original version of Dijkstra's algorithm, it only tries to find the minimal path between two nodes, but more commonly the modern variant can find the shortest paths from a single source to all other nodes, producing a shortest path tree.

Specifically, for each edge (u, v) in a non-negative weighted graph G, maintain a set S of vertices whose final shortest paths have been computed. Repeatedly select 𝓊 out of V - S with minimum shortest path estimate, add 𝓊 to S and relax all edges adjacent and reachable from 𝓊.

DIJKSTRA(graph, source)
  Initialize d array to either Infinity or 0 (s = source)
  Initialize π array of vertices with their self
  set S := empty
  Q := a priority queue of reachable vertices from source
  while Q != empty
    u = EXTRACT_MIN(Q)    // deletes a vertex with minimal distance to the source
    S.add(u)
    for vertex v adjacent to u
      RELAX(u, v, d, π)

  output array d and π

RELAX(u, v, d, π)
  if d[v] > d[u] + w(u, v)
    d[v] = d[u] + w(u, v)
    π[v] = u;

Figure 3. An Example of Dijkstra's Algorithm

Bellman-Ford Algorithm

Though slower than peer shortest path algorithm like Dijkstra's, Bellman-Ford algorithm can compute the shortest paths from a single source that might bear negative edges in between.

Specifically, given a graph G = (V, E), this algorithm answers true if a shortest path exists from a single source to a destination without cycles, otherwise answers false;

BELLMAN_FORD(graph, source)
  Initialize d array to either Infinity or 0 (s = source)
  Initialize π array of vertices with their self
  for i := 1 to |V| - 1
    for each edge (u, v) ∈ E
      RELAX(u, v, d, π)   // same sub-routine as Dijkstra
  for edge (u, v) ∈ E
    if d[v] > d[u] + w(u, v)
      report a negative cycle exists, return false
  return true

Note: why do we care about negative edges? reasons include computational tasks in a water pipeline or electric wires, or financial models with various cost and revenue gains in many vertices.

Additional References

1. Shortest Paths II, MIT OpenCourseware, https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec16.pdf