All-Pairs Shortest Path

Floyd-Warshall's Algorithm

Description:

Floyd-Warshall's algorithm solves the problem of finding the shortest path betweeen two vertices u and v. It is a Dynamic Programming solution. This problem is known by All-pairs shortest paths.

Input:

Given a connected and weighted graph G(E, V) where V <= 400

Output:

It returns the shortest path between u and v as dist[u][v]

Implementation:

int dist[1000][1000];
int weight[1000][1000];

void floyd_warshall(int n) {
  for (int i = 0; i < n; i++) 
    for (int j = 0; j < n; j++) 
      dist[i][j] = i == j ? 0 : weight[i][j];

  for (int k = 0; k < n; k++) 
    for (int i = 0; i < n; i++) 
       for (int j = 0; j < n; j++) 
          dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}