Single Source Shortest Path (SSSP) in a graph

Unweighted graph

We call a shortest path from vertex $u$ to vertex $v$ a path of length $k$ where the path consists of vertices $p = (x_1, x_2, \ldots, x_k)$ such that $x_1 = u, x_k = v$ and $k$ is minimum

In an unweighted graph, breadth first search guarantees that when we analyze a vertex $v$ it will actually hold the shortest path to it, more searching will never find a path $uv$ to $v$ with fewer edges

let $d(v)$ be the shortest distance from a vertex $v$ to $s$, initially $d(v) = \infty, v \not= s$ and $d(s) = 0$
whenever a vertex $v$ where $d(v) = \infty$ is reached by some other vertex $u$ whose $d(u)$ was already computed then $d(v) = d(u) + 1$

/**
 * Breadth first search algorithm applied on an unweighted graph `G`
 * of order `n` and size `m` to find the shortest path from a source
 * vertex `s`
 *
 * Time complexity: O(n + m)
 * Space complexity: O(n)
 *
 * @param {vector<vector<int> >} g The adjacency list representation
 *  of `G`, each entry `g_{ij}` holds the end `v` of the edge `iv`
 * @param {int} s The source vertex
 * @return {vector<int>} The shortest path from `s` to all the other vertices
 */
vector<int> bfs(vector<vector<int> > &g, int s) {
  int n = g.size();

  // the vertex predecessor of `i` in the `s-i` path
  vector<int> parent(n, -1);
  // holds the shortest distance from `s` to vertex `i`
  vector<int> d(n, INF);

  // the distance from the source vertex is zero
  d[s] = 0;

  // accumulated weight, next vertex (weight, v)
  queue<int> q;
  q.push(s);

  while (!q.empty()) {
    int v = q.front();
    q.pop();

    for (int i = 0; i < g[v].size(); i += 1) {
      int to = g[v][i];
      if (d[to] == INF) {
        d[to] = d[v] + 1;
        parent[to] = v;
        q.push(to);
      }
    }
  }

  return d;
}

Weighted graph

Dijkstra’s algorithm

Dijkstra described an algorithm to solve the SSSP, there are some additional states that need to be stored per vertex:

let $d(v)$ be an estimate of the shortest distance from a vertex $v$ to $s$, initially $d(v) = \infty, v \not= s$ and $d(s) = 0$
let $visited(v)$ be the visited state of a given vertex, initially $visited(v) = false$

The algorithm consists in a series of iterations, on each iteration let $u$ be the vertex with the minimum distance to $s$ that wasn’t visited yet, a process called relaxation is the performed with $u$

the visited state is set to true, i.e. $visited(v) = true$
let $uv$ be an edge to an unvisited node $v$ with weight $w(uv)$, we might improve the best estimate of the shortest path between $u$ and $v$ by including $uv$ in the path so

$$ d(v) = min(d(v), d(u) + w(uv)) $$

After $n$ iterations all the vertices will be marked and $d(v)$ state will hold the shortest path from $s$ to all the other vertices

We need a data structure that supports the following 3 operations quickly:

remove a vertex with the minimum distance that wasn’t discovered yet (up to once for each vertex in the graph)
add a new vertex (up to once for each vertex in the graph)
update the estimated distance of an existing vertex (once for each edge in the graph)

Implementation with an array

An array supports the operations above in $O(V)$, $O(1)$, and $O(1)$ respectively leading to an overall $O(V^2 + E)$ which is optimal for dense graphs (when $E \approx V^2$)

/**
 * An implementation of Dijkstra's algorithm which computes
 * the shortest path from a source vertex `s` to all the other vertices
 * in a graph `G` with `V` vertices and `E` edges.
 *
 * Time complexity: O(V^2 + E)
 * Space complexity: O(V)
 *
 * @param {vector<vector<pair<int, int> > >} g The adjacency list representation
 *  of `G`, each entry `g_{ij}` holds the end `v` of the edge `iv` and the weight
 *  `weight` of the edge i.e. (v, weight)
 * @param {int} s The source vertex
 * @return {vector<int>} The shortest path from `s` to all the other vertices
 */
vector<int> dijkstra(vector<vector<pair<int, int> > > &g, int s) {
  int V = g.size();
  int INF = 1e9;

  vector<bool> visited(V);
  // the vertex predecessor of `i` in the `s-i` path
  vector<int> parent(V, -1);
  // holds the estimated distance
  vector<int> d(V, INF);

  // the estimated distance from the source vertex is zero
  d[s] = 0;

  for (int i = 0; i < V; i += 1) {
    // the vertex with the minimum estimated distance
    int v = -1;
    for (int j = 0; j < V; j += 1) {
      // find the vertices which haven't been visited yet
      // among them find a vertex with the minimum estimated distance
      if (!visited[j] && (v == -1 || d[j] < d[v])) {
        v = j;
      }
    }

    if (d[v] == INF) {
      // the vertex selected is not reachable from `s`
      break;
    }

    visited[v] = true;

    // update the estimated distance from `v`
    // to all the other adjacent vertices
    for (int j = 0; j < g[v].size(); j += 1) {
      pair<int, int> &edge = g[v][j];
      int next = edge.first;
      int weight = edge.second;
      int new_distance = d[v] + weight;

      if (new_distance < d[next]) {
        d[next] = new_distance;
        parent[next] = v;
      }
    }
  }

  return d;
}

Implementation with a BST

A balanced searth tree supports the operations above in $O(\log V)$, $O(\log V)$, and $O(\log V)$ respectively leading to an overal $O((E + V) \log V)$ time complexity optimal for sparse graphs (when $E \approx V$)

/**
 * C++11
 *
 * An implementation of Dijkstra's algorithm which computes
 * the shortest path from a source vertex `s` to all the other vertices
 * in a graph `G` of order `V` and size `E`
 *
 * Time complexity: O((E+V) log V)
 * Space complexity: O(V)
 *
 * @param {vector<vector<pair<int, int>>>} g The adjacency list representation
 *  of `G`, each entry `g_{ij}` holds a pair which represents an edge
 * (vertex, weight) which tells that there's an edge from `i` to `vertex`
 * with weight `weight`
 * @param {int} s The source vertex
 * @return {vector<int>} The shortest path from `s` to all the other vertices
 */
int dijkstra(vector<vector<pair<int, int>>> &g, int source) {
  int V = g.size();
  int INF = 1e9;
  int total = 0;

  // the vertex predecessor of `i` in the `s-i` path
  vector<int> parent(V, -1);
  // holds the estimated distance
  vector<int> d(V, INF);

  // the estimated distance from the source vertex is zero
  d[s] = 0;

  // accumulated weight, next vertex (weight, v)
  set<pair<int, int>> q;
  q.insert({0, s});

  while (!q.empty()) {
    pair<int, int> edge = *(q.begin());
    int from = edge.second;
    q.erase(q.begin());

    for (int i = 0; i < g[v].size(); i += 1) {
      int to, weight;

      // note that in the graph the first element is the neighbor vertex
      // but in the set the first element is the edge weight
      tie(to, weight) = g[v][i];

      if (d[from] + weight < d[to]) {
        q.erase({ d[to], to });
        d[to] = d[from] + weight;
        parent[to] = v;
        q.insert({ d[to], to });
      }
    }
  }

  return d;
}

Applications

Find the shortest path between two vertices $u$ and $v$
Find the shortest path from all the vertices to a given vertex $v$ by reversing the direction of each edge in the graph
Find the shortest path for every pair of vertices $u$ and $v$ by running the algorithm once per vertex