The shortest path algorithm finds paths between two vertices in a graph such that total sum of the constituent edge 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]
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 to the process of repeatedly improving the shortest path approximations from a source vertex s to every vertex v in a graph
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
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 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
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 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
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 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
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 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)
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)