All-Pairs Shortest-Paths Problem

The all-pairs shortest paths problem aims to find the shortest distance between every pair of vertices in a graph. Dynamic programming algorithms like Floyd-Warshall can solve this in O(V^3) time.

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// Floyd-Warshall algorithm
int[][] floydWarshall(int[][] graph) {
  int V = graph.length;
  int[][] dist = new int[V][V];
  
  // Initialize distances
  for (int i = 0; i < V; i++) {
    for (int j = 0; j < V; j++) {
      dist[i][j] = graph[i][j];
    }
  }
  
  // Find shortest paths 
  for (int k = 0; k < V; k++) {
    for (int i = 0; i < V; i++) {
      for (int j = 0; j < V; j++) {
        if (dist[i][k] + dist[k][j] < dist[i][j]) {
          dist[i][j] = dist[i][k] + dist[k][j]; 
        }
      }
    }
  }
  
  return dist;
}

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// Floyd-Warshall algorithm
vector<vector<int>> floydWarshall(vector<vector<int>> graph) {
  int V = graph.size();
  vector<vector<int>> dist(V, vector<int>(V));

  for (int i = 0; i < V; i++) {
    for (int j = 0; j < V; j++) {
      dist[i][j] = graph[i][j]; 
    }
  }

  for (int k = 0; k < V; k++) {
    for (int i = 0; i < V; i++) {
      for (int j = 0; j < V; j++) {
        if (dist[i][k] + dist[k][j] < dist[i][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }

  return dist;
}

Python example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

# Floyd-Warshall algorithm
def floyd_warshall(graph):
  V = len(graph)
  dist = [[float("inf") for _ in range(V)] for _ in range(V)]

  for i in range(V):
    for j in range(V):
      dist[i][j] = graph[i][j]
  
  for k in range(V):
    for i in range(V):
      for j in range(V):
        if dist[i][k] + dist[k][j] < dist[i][j]:
          dist[i][j] = dist[i][k] + dist[k][j]

  return dist

Enables solving various graph analysis problems efficiently including presence of negative cycles. Useful for network routing, economics, and bioinformatics.

The All-Pairs Shortest-Paths problem is focused on finding the shortest paths between all pairs of vertices in a weighted graph. Algorithms like Floyd-Warshall and Johnson’s algorithm are often used for this. It’s useful in applications where you need to know the shortest distances between all pairs of nodes, not just from a single source.

Algorithm

  1. Initialization: Create a 2D matrix where the value at (i, j) is initialized to the weight of the edge from i to j, or infinity if no such edge exists.
  2. Iteration: For each pair of vertices (i, j), update the shortest path using all possible intermediate vertices.
  3. Final Matrix: The final 2D matrix will have the shortest path from each vertex i to each vertex j.

Java Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public class AllPairsShortestPath {
    public static int[][] floydWarshall(int[][] graph) {
        int n = graph.length;
        int[][] dist = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = graph[i][j];
                if (i != j && graph[i][j] == 0) {
                    dist[i][j] = Integer.MAX_VALUE;
                }
            }
        }

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE &&
                        dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
        return dist;
    }
}

C++ Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <vector>
#include <limits.h>

std::vector<std::vector<int>> floydWarshall(std::vector<std::vector<int>> graph) {
    int n = graph.size();
    std::vector<std::vector<int>> dist(n, std::vector<int>(n, 0));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dist[i][j] = graph[i][j];
            if (i != j && graph[i][j] == 0) {
                dist[i][j] = INT_MAX;
            }
        }
    }

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX &&
                    dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    return dist;
}

Python Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def floyd_warshall(graph):
    n = len(graph)
    dist = [[0 for _ in range(n)] for _ in range(n)]
    
    for i in range(n):
        for j in range(n):
            dist[i][j] = graph[i][j]
            if i != j and graph[i][j] == 0:
                dist[i][j] = float('inf')

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] != float('inf') and dist[k][j] != float('inf') and \
                   dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

The time complexity for Floyd-Warshall is (O(V^3)). It’s not the most efficient for large graphs, but it’s straightforward and works for graphs with negative edge weights as long as there are no negative cycles.