## 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

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