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(V2)

  • 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(V3)

  • Space complexity: O(V)