The shortest path is an algorithm to find a path between two vertices in a graph such that the total sum of the weights of the constituent edges is minimum. In the following graph, between vertex 3 and 1, there are two paths including [3, 2, 1] costs 9 (4 + 5) and [3, 2, 0, 1] costs 7 (4 + 1 + 2). The shortest path is [3, 2, 0, 1]

In this article, you will learn to implement the Shortest Path Algorithms with Breadth-First Search (BFS), Dijkstra, Bellman-Ford, and Floyd-Warshall algorithms

BFS algorithm is used to find the shortest paths from a single source vertex in an unweighted graph

Dijkstra algorithm is used to find the shortest paths from a single source vertex in a nonnegative-weighted graph

Bellman-Ford and Floyd-Warshall algorithms are used to find the shortest paths in a negative-weighted graph which has both non-negative and negative weights. While Bellman-Ford is used to find from a single source vertex, Floyd-Warshall is used to find from all pairs of vertices

### Edge Relaxation

Dijkstra and Bellman-Ford algorithms work based on a technique known as edge relaxation which is an analogy between the process of repeatedly improving the shortest path approximations from a source vertex s to every vertex v and the relaxation of a helical tension spring

Let's get started

### Problem 1: Single-source Shortest Paths in an Unweighted Graph

Given an unweighted graph G = (V, E) and a single source vertex s in V

Write an algorithm to find the shortest path from s to every vertex in V

### Example 1

- Input: Given a directed unweighted graph G = (V, E) with V = 4 and E = [[0, 1], [2, 0], [2, 1], [3, 2]]

- Output 1: With the finding started at source vertex s = 3

```
Vertex Distance from source Route from source
0 2 [3, 2, 0]
1 2 [3, 2, 1]
2 1 [3, 2]
3 0 [3]
```

- Output 2: With the finding started at source vertex s = 2

```
Vertex Distance from source Route from source
0 1 [2, 0]
1 1 [2, 1]
2 0 [2]
3 N/A N/A
```

### Approach 1: BFS Algorithm

In the above example, to calculate the distance from the source vertex 3 to 1, you can compute and combine the distance from 3 to 2 and 2 to 1

Lets use an array d[V] to store the approximate distance from s to every vertex v in V. Init d[v] = Infinity value for every vertex v, except d[s] = 0, then

```
d[3] = 0
d[2] = d[3] + 1 = 1
d[1] = d[2] + 1 = 2
d[0] = d[2] + 1 = 2
In general, d[v] = d[u] + 1 for every edge (u, v) in the graph
```

```
```

`GraphDirectedByAdjacencyList`

is defined in Graph Data Structure Tutorial

Time complexity: O(V+E)

Space complexity: O(V)

### Problem 2: Single-source Shortest Paths in a NonNegative-Weighted Graph

Given a nonnegative-weighted graph G = (V, E) and a single source vertex s in V

Write an algorithm to find the shortest path from s to every vertex in V

### Example 2

- Input: Given a directed nonnegative-weighted graph G = (V, E) with V = 4 and E = [[0, 1, 2], [2, 0, 1], [2, 1, 5], [3, 2, 4]]

- Output: With the finding started at source vertex s = 3

```
Vertex Distance from source Route from source
0 5 [3, 2, 0]
1 7 [3, 2, 0, 1]
2 4 [3, 2]
3 0 [3]
```

- Output: With the finding started at source vertex s = 2

```
Vertex Distance from source Route from source
0 1 [2, 0]
1 3 [2, 0, 1]
2 0 [2]
3 N/A N/A
```

Why BFS doesn't work on a weighted graph? Says you find the shortest path from 3 to 1

BFS: [3, 2, 1] costs 9

Shortest path (minimum cost path): [3, 2, 0, 1] costs 7

### Approach 2.1: Dijkstra Algorithm

- Let's use an array d[V] to store the approximate distance from s to every vertex v in V. Init d[v] = Infinity value for every vertex v, except d[s] = 0, then with the above example

```
d[3] = 0
for edge (3, 2), d[2] = min(d[2], d[3] + 4)
for edge (2, 0), d[0] = min(d[0], d[2] + 1)
for edge (2, 1), d[1] = min(d[1], d[2] + 5)
for edge (0, 1), d[1] = min(d[1], d[0] + 2)
In general, d[v] = min(d[v], d[u] + weight(u,v)) for every edge (u, v) in the graph
```

```
```

`GraphWeightedByAdjacencyList`

is defined in Graph Data Structure Tutorial

Time complexity: O(V

^{2})Space complexity: O(V)

### Approach 2.2: Dijkstra Algorithm with Min Heap

- A min-heap (priority queue) is used to greedily pick the unvisited and closest vertex u and perform relaxation for every edge (u, v) comes out from u

```
```

`GraphWeightedByAdjacencyList`

is defined in Graph Data Structure Tutorial

Time complexity: O((E + V) log V)

Space complexity: O(V)

### Problem 3: Single-source Shortest Paths in a Negative-Weighted Graph

Given a negative-weighted graph G = (V, E) and a single source vertex s in V

Write an algorithm to find the shortest path from s to every vertex in V

Returns an error message if the input graph has a negative weight cycle

### Example 3.1

Input: Given a directed graph G = (V, E) with V = 4 and E = [[0, 1, -2], [2, 0, 1], [2, 1, 3], [3, 2, 4]]

Output: With the finding started at source vertex s = 3

```
Vertex Distance from source Route from source
0 5 [3, 2, 0]
1 3 [3, 2, 0, 1]
2 4 [3, 2]
3 0 [3]
```

### Example 3.2

Input: Given a directed graph G = (V, E) with V = 4 and E = [[0, 1, -5], [2, 0, 1], [1, 2, 3], [3, 2, 4]]

Output: With the finding started at any source vertex

```
The input graph contains a negative-weight cycle
```

### Approach 3: Bellman-Ford Algorithm

In the first example, from source vertex 3 to 1, there are 2 paths [3, 2, 1] costs 7 (4 + 3) and [3, 2, 0, 1] costs 3 (4 + 1 - 2), the shortest path is [3, 2, 0, 1]

Let's use an array d[V] to store the approximate distance from s to every vertex v in V. Init d[v] = Infinity value for every vertex v, except d[s] = 0, then with the above example

```
d[3] = 0
for edge (3, 2), d[2] = min(d[2], d[3] + 4)
for edge (2, 0), d[0] = min(d[0], d[2] + 1)
for edge (2, 1), d[1] = min(d[1], d[2] + 3)
for edge (0, 1), d[1] = min(d[1], d[0] - 2)
In general, d[v] = min(d[v], d[u] + weight(u,v)) for every edge (u, v) in the graph
```

Bellman-Ford algorithm doesn't work with a negative-weighted cycle. In the second example, 3 edges (2, 0), (0, 1), and (1, 0) forms a negative-weighted cycle (sum of weights is -1)

Dijkstra algorithm uses a priority queue to greedily pick the unvisited and closest vertex u and perform relaxation for every edge (u, v) comes out from u. Bellman-Ford algorithm doesn't use a queue, but do the relaxation for all edges V-1 times

Bellman-Ford algorithm is slower but more versatile than Dijkstra algorithm as it can work with negative weight edges

```
```

`GraphWeightedByAdjacencyList`

is defined in Graph Data Structure Tutorial

Time complexity: O(VE)

Space complexity: O(V)

### Problem 4: All-pairs Shortest Paths in a Negative-Weighted Graph

Given a negative-weighted graph G = (V, E) and a single source vertex s in V

Write an algorithm to find the shortest path from all-pairs of vertices in V

Returns an error message if the input graph has a negative weight cycle

### Example 4.1

- Input: Given a directed graph G which represented as the following matrix, I denotes the infinity value

```
0 -2 I I
I 0 I I
1 3 0 I
I I 4 0
```

- Output: With the finding started from all-pairs of vertices

```
0 -2 I I
I 0 I I
1 -1 0 I
5 3 4 0
```

### Example 4.2

- Input: Given a directed graph G which represented as the following matrix, I denotes the infinity value

```
0 -5 I I
I 0 3 I
1 I 0 I
I I 4 0
```

- Output: With the finding started from all-pairs of vertices

```
The input graph contains a negative-weight cycle
```

### Approach 4: Floyd-Warshall Algorithm

The algorithm incrementally improving an estimate on the shortest path between all pairs of vertices (i, j) by comparing all possible paths between the pair

For each pair of vertices (i, j), the shortest path between them is a min value of the path from i to j and the paths between i to k and k to j with k are intermediate vertices

Floyd-Warshall algorithm doesn't work with a negative-weighted cycle. In the second example, 3 edges (2, 0), (0, 1), and (1, 0) forms a negative-weighted cycle (sum of weights is -1)

```
```

Time complexity: O(V

^{3})Space complexity: O(V)