HelloKoding

Practical coding guides

Shortest Path Algorithms

In this article, you will learn to find shortest paths in a graph by using Breadth-First Search (BFS), Dijkstra, Bellman-Ford, and Floyd-Warshall algorithms

The shortest path problem is about finding paths between vertices in a graph such that the total sum of the edges weights 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]

A directed positive-weighted graph

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 paths 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]]
A directed unweighted graph
  • 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

ShortestPathByBFS.java

package com.hellokoding.datastructure.graph;

import java.util.*;

public class ShortestPathByBFS {
    static final int INFINITE = Integer.MAX_VALUE;
    static final int UNDEFINED = -1;

    public static Object[] shortestPathByBFS(GraphDirectedByAdjacencyList g, int source) {
        int[] distances = new int[g.getV()];
        int[] predecessors = new int[g.getV()];

        for (int v = 0; v < g.getV(); v++) {
            distances[v] = INFINITE;
            predecessors[v] = UNDEFINED;
        }
        distances[source] = 0;

        boolean[] visited = new boolean[g.getV()];
        visited[source] = true;

        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(source);

        while (!queue.isEmpty()) {
            int u = queue.poll();

            for (int v : g.getAdjacencyList().get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    distances[v] = distances[u] + 1;
                    predecessors[v] = u;
                    queue.offer(v);
                }
            }
        }

        return new Object[]{distances, predecessors};
    }

    static void printResult(Object[] paths) {
        int[] distancesFromSource = (int[]) paths[0];
        int[] predecessorsOfSource = (int[]) paths[1];

        System.out.println("Vertex\tDistance from source\tRoute from source");
        for (int v = 0; v < distancesFromSource.length; v++) {
            if (distancesFromSource[v] == INFINITE) {
                System.out.printf("%-8s%-24s%s%s", v, "N/A", "N/A", System.lineSeparator());
                continue;
            }

            Deque<Integer> route = new ArrayDeque<>();
            route.push(v);
            int u = predecessorsOfSource[v];
            while (u >= 0) {
                route.push(u);
                u =  predecessorsOfSource[u];
            }

            System.out.printf("%-8d%-24d%s%s", v, distancesFromSource[v], route.toString(), System.lineSeparator());
        }
    }

    public static void main(String[] args) {
        GraphDirectedByAdjacencyList g = new GraphDirectedByAdjacencyList(4);
        g.addEdge(0, 1);
        g.addEdge(2, 0);
        g.addEdge(2, 1);
        g.addEdge(3, 2);
        printResult(shortestPathByBFS(g, 3));
        printResult(shortestPathByBFS(g, 2));
    }
}

GraphDirectedByAdjacencyList is defined in Graph Data Structure

  • 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 positive-weighted graph G = (V, E) with V = 4 and E = [[0, 1, 2], [2, 0, 1], [2, 1, 5], [3, 2, 4]]
A directed positive-weighted graph
  • 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

ShortestPathByDijkstra.java

package com.hellokoding.datastructure.graph;

import java.util.*;

import static com.hellokoding.datastructure.graph.GraphWeightedByAdjacencyList.WeightedVertex;

public class ShortestPathByDijkstra {
    static final int INFINITE = Integer.MAX_VALUE;
    static final int UNDEFINED = -1;

    static int minVertex(Queue<Integer> queue, int[] distance) {
        int minDistance = INFINITE;
        int minVertex = UNDEFINED;

        for (Integer v : queue) {
            if (minDistance > distance[v]) {
                minDistance = distance[v];
                minVertex = v;
            }
        }

        return minVertex;
    }

    static Object[] shortestPathByDijkstra(GraphWeightedByAdjacencyList g, int source) {
        int[] distances = new int[g.getV()];
        int[] predecessors = new int[g.getV()];
        Queue<Integer> queue = new ArrayDeque<>();

        for (int v = 0; v < g.getV(); v++) {
            distances[v] = INFINITE;
            predecessors[v] = UNDEFINED;
            queue.offer(v);
        }
        distances[source] = 0;

        while (!queue.isEmpty()) {
            int u = minVertex(queue, distances);
            if (u == UNDEFINED)  break;
            queue.remove(u);

            for (WeightedVertex v : g.getAdjacencyList().get(u)) {
                if (distances[u] == INFINITE) continue;

                int alt = distances[u] + v.weight;
                if (alt < distances[v.vertex]) {
                    distances[v.vertex] = alt;
                    predecessors[v.vertex] = u;
                }
            }
        }

        return new Object[]{distances, predecessors};
    }

    static void printResult(Object[] paths) {
        int[] distances = (int[]) paths[0];
        int[] predecessors = (int[]) paths[1];

        System.out.println("Vertex\tDistance from source\tRoute from source");
        for (int v = 0; v < distances.length; v++) {
            if (distances[v] == INFINITE) {
                System.out.printf("%-8s%-24s%s%s", v, "N/A", "N/A", System.lineSeparator());
                continue;
            }

            Deque<Integer> route = new ArrayDeque<>();
            route.push(v);
            int u = predecessors[v];
            while (u >= 0) {
                route.push(u);
                u =  predecessors[u];
            }

            System.out.printf("%-8d%-24d%s%s", v, distances[v], route.toString(), System.lineSeparator());
        }
    }

    public static void main(String[] args) {
        GraphWeightedByAdjacencyList g = new GraphWeightedByAdjacencyList(4);
        g.addEdge(0, 1, 2);
        g.addEdge(2, 0, 1);
        g.addEdge(2, 1, 5);
        g.addEdge(3, 2, 4);
        printResult(shortestPathByDijkstra(g, 3));
        printResult(shortestPathByDijkstra(g, 2));
    }
}

GraphWeightedByAdjacencyList is defined in Graph Data Structure

  • 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

ShortestPathByDijkstraWithMinHeap.java

package com.hellokoding.datastructure.graph;

import java.util.*;

import static com.hellokoding.datastructure.graph.GraphWeightedByAdjacencyList.WeightedVertex;

public class ShortestPathByDijkstraWithMinHeap {
    static final int INFINITE = Integer.MAX_VALUE;
    static final int UNDEFINED = -1;

    static Object[] shortestPathByDijkstra(GraphWeightedByAdjacencyList g, int source) {
        int[] distances = new int[g.getV()];
        int[] predecessors = new int[g.getV()];
        PriorityQueue<WeightedVertex> minHeap = new PriorityQueue<>(g.getV(), Comparator.comparingInt(WeightedVertex::getWeight));

        for (int v = 0; v < g.getV(); v++) {
            distances[v] = INFINITE;
            predecessors[v] = UNDEFINED;
            minHeap.add(new WeightedVertex(v, distances[v]));
        }
        distances[source] = 0;

        while (!minHeap.isEmpty()) {
            WeightedVertex u = minHeap.poll();

            for (WeightedVertex v : g.getAdjacencyList().get(u.vertex)) {
                if (distances[u.vertex] == INFINITE) continue;

                int alt = distances[u.vertex] + v.weight;
                if (alt < distances[v.vertex]) {
                    distances[v.vertex] = alt;
                    predecessors[v.vertex] = u.vertex;
                }
            }
        }

        return new Object[]{distances, predecessors};
    }

    static void printResult(Object[] paths) {
        int[] distances = (int[]) paths[0];
        int[] predecessors = (int[]) paths[1];

        System.out.println("Vertex\tDistance from source\tRoute from source");
        for (int v = 0; v < distances.length; v++) {
            if (distances[v] == INFINITE) {
                System.out.printf("%-8s%-24s%s%s", v, "N/A", "N/A", System.lineSeparator());
                continue;
            }

            Deque<Integer> route = new ArrayDeque<>();
            route.push(v);
            int u = predecessors[v];
            while (u >= 0) {
                route.push(u);
                u =  predecessors[u];
            }

            System.out.printf("%-8d%-24d%s%s", v, distances[v], route.toString(), System.lineSeparator());
        }
    }

    public static void main(String[] args) {
        GraphWeightedByAdjacencyList g = new GraphWeightedByAdjacencyList(4);
        g.addEdge(0, 1, 2);
        g.addEdge(2, 0, 1);
        g.addEdge(2, 1, 5);
        g.addEdge(3, 2, 4);
        printResult(shortestPathByDijkstra(g, 3));
        printResult(shortestPathByDijkstra(g, 2));
    }
}

GraphWeightedByAdjacencyList is defined in Graph Data Structure

  • 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
A negative-weighted graph

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

ShortestPathByBellmanFord.java

package com.hellokoding.datastructure.graph;

import java.util.*;

public class ShortestPathByBellmanFord {
    static final int INFINITE = Integer.MAX_VALUE;
    static final int UNDEFINED = -1;

    static Object[] shortestPathByBellmanFord(GraphWeightedByAdjacencyList g, int source) {
        int[] distances = new int[g.getV()];
        int[] predecessors = new int[g.getV()];

        for (int v = 0; v < g.getV(); v++) {
            distances[v] = INFINITE;
            predecessors[v] = UNDEFINED;
        }
        distances[source] = 0;

        for (int i = 1; i < g.getV(); i++) {
            for (int u = 0; u < g.getV(); u++) {
                for (GraphWeightedByAdjacencyList.WeightedVertex v : g.getAdjacencyList().get(u)) {
                    if (distances[u] == INFINITE) continue;
                    int alt = distances[u] + v.weight;
                    if (alt < distances[v.vertex]) {
                        distances[v.vertex] = alt;
                        predecessors[v.vertex] = u;
                    }
                }
            }
        }

        for (int u = 0; u < g.getV(); u++) {
            for (GraphWeightedByAdjacencyList.WeightedVertex v : g.getAdjacencyList().get(u)) {
                if (distances[u] == INFINITE) continue;
                int alt = distances[u] + v.weight;
                if (alt < distances[v.vertex]) {
                    System.out.println("The input graph contains a negative-weight cycle");
                    return new Object[]{};
                }
            }
        }

        return new Object[]{distances, predecessors};
    }

    static void printResult(Object[] paths) {
        if (paths.length == 0) return;

        int[] distances = (int[]) paths[0];
        int[] predecessors = (int[]) paths[1];

        System.out.println("Vertex\tDistance from source\tRoute from source");
        for (int v = 0; v < distances.length; v++) {
            if (distances[v] == INFINITE) {
                System.out.printf("%-8s%-24s%s%s", v, "N/A", "N/A", System.lineSeparator());
                continue;
            }

            Deque<Integer> route = new ArrayDeque<>();
            route.push(v);
            int u = predecessors[v];
            while (u >= 0) {
                route.push(u);
                u =  predecessors[u];
            }

            System.out.printf("%-8d%-24d%s%s", v, distances[v], route.toString(), System.lineSeparator());
        }
    }

    public static void main(String[] args) {
        GraphWeightedByAdjacencyList g1 = new GraphWeightedByAdjacencyList(4);
        g1.addEdge(0, 1, -2);
        g1.addEdge(2, 0, 1);
        g1.addEdge(2, 1, 3);
        g1.addEdge(3, 2, 4);
        printResult(shortestPathByBellmanFord(g1, 3));

        GraphWeightedByAdjacencyList g2 = new GraphWeightedByAdjacencyList(4);
        g2.addEdge(0, 1, -5);
        g2.addEdge(2, 0, 1);
        g2.addEdge(1, 2, 3);
        g2.addEdge(3, 2, 4);
        printResult(shortestPathByBellmanFord(g2, 3));
    }
}

GraphWeightedByAdjacencyList is defined in Graph Data Structure

  • 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
A negative-weighted graph

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)

ShortestPathByFloydWarshall.java

package com.hellokoding.datastructure.graph;

import java.util.Arrays;

public class ShortestPathByFloydWarshall {
    static final int I = Integer.MAX_VALUE;

    public static int[][] shortestPathByBFSFloydWarshall(int[][] g) {
        int V = g.length;
        int[][] distances = Arrays.copyOf(g, V);

        for (int k = 0; k < V; k++) {
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    if (distances[i][k] == I || distances[k][j] == I) continue;
                    distances[i][j] = Math.min(distances[i][j], distances[i][k] + distances[k][j]);
                }

                if (distances[i][i] < 0) {
                    System.out.println("The input graph contains a negative-weight cycle");
                    return new int[][]{};
                }
            }
        }

        return distances;
    }

    static void printResult(int[][] distances) {
        int V = distances.length;
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                System.out.printf("%-4s", distances[i][j] == I ? "I" : distances[i][j]);
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[][] g1 = new int[][] {
            {0, -2, I, I},
            {I, 0, I, I},
            {1, 3, 0, I},
            {I, I, 4, 0}
        };
        printResult(shortestPathByBFSFloydWarshall(g1));

        int[][] g2 = new int[][] {
            {0, -5, I, I},
            {I, 0, 3, I},
            {1, I, 0, I},
            {I, I, 4, 0}
        };
        printResult(shortestPathByBFSFloydWarshall(g2));
    }
}
  • Time complexity: O(V3)
  • Space complexity: O(V)
Follow HelloKoding