Given a weighted graph $$G$$ of order $$n$$ and size $$m$$ where all the weights are non-negative and given a source vertex $$s$$, the single source shortest path problem consists in finding the distance from $$s$$ to all the other vertices

## 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(n)$$, $$O(1)$$, and $$O(1)$$ respectively leading to an overall $$O(n^2 + m)$$ which is optimal for dense graphs (when $$m \approx n^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 of order n and size m
*
* Time complexity: O(n^2 + m)
* Space complexity: O(n)
*
* @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 n = g.size();
int INF = 1e9;

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

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

for (int i = 0; i < n; i += 1) {
// the vertex with the minimum estimated distance
int v = -1;
for (int j = 0; j < n; 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 an BST

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

/**
* 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 n and size m
*
* Time complexity: O(m log n)
* Space complexity: O(n)
*
* @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 n = g.size();
int INF = 1e9;
int total = 0;

// the vertex predecessor of i in the s-i path
vector<int> parent(n, -1);
// holds the estimated distance
vector<int> d(n, 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 v = edge.second;
q.erase(q.begin());

for (int i = 0; i < g[v].size(); i += 1) {
pair<int, int> next = g[v][i];

// note that in the graph the first element is the neighbor vertex
// but in the set the first element is the edge weight
int to = next.first;
int weight = next.second;
int new_distance = d[to] + weight;

if (new_distance < d[to]) {
q.erase({ d[to], to });
d[to] = new_distance;
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