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,\dots ,x_k)$ such that $x_1=u$, $x_k=v$, and $k$ is minimum.

In an unweighted graph, a 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 to $v$ with fewer edges.

• Let $d(v)$ be the shortest distance from a vertex $v$ to $s$. Initially, $d(v)=\mathrm{\infty }$ for $v\ne s$ and $d(s)=0$.
• Whenever a vertex $v$ where $d(v)=\mathrm{\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)=\mathrm{\infty }$ for $v\ne s$ and $d(s)=0$.
• Let $visited(v)$ be the visited state of a given vertex. Initially, $visited(v)=false$.

The algorithm consists of a series of iterations. In each iteration, let $u$ be the vertex with the minimum distance to $s$ that hasn’t been visited yet. A process called relaxation is then performed with $u$.

• The visited state is set to true, i.e., $visited(u)=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 $s$ and $v$ by including $uv$ in the path, so:

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

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

• Remove a vertex with the minimum distance that hasn’t been 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 time complexity of $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 search tree supports the operations above in $O(\log V)$, $O(\log V)$, and $O(\log V)$, respectively, leading to an overall $O((E+V)\log V)$ time complexity, which is 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 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.