Floyd-Warshall Algorithm Guide

Floyd-Warshall Algorithm

The Floyd-Warshall algorithm is a classic dynamic programming method used to find the shortest paths between all pairs of vertices in a weighted graph (can handle negative weights but not negative cycles).

Algorithm Explanation

Let dist[i][j] be the shortest distance from vertex i to j. Initialize dist[i][j] to the weight of edge (i, j), or infinity if no edge exists. The diagonal dist[i][i] is set to 0. For each vertex k, check if going through k shortens the path from i to 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];

Complexity

  • Time Complexity: O(V3)
  • Space Complexity: O(V2)

Easy Problems

1. Find All Pairs Shortest Paths

Given a graph, compute shortest distances between every pair of vertices.

const int INF = 1e9;
const int V = 4;
int graph[V][V] = {
  {0, 5, INF, 10},
  {INF, 0, 3, INF},
  {INF, INF, 0, 1},
  {INF, INF, INF, 0}
};

void floydWarshall(int dist[V][V]) {
  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];
}

2. Detect Reachability Between Nodes

Using Floyd-Warshall, determine if a path exists between two vertices.

bool reachable(int dist[V][V], int u, int v) {
  return dist[u][v] < INF;
}

Intermediate Problems

1. Find the Graph Center

The center is the node with the minimum maximum distance to all other nodes.

int findGraphCenter(int dist[V][V]) {
  int center = -1, minMaxDist = INF;
  for (int i = 0; i < V; i++) {
    int maxDist = 0;
    for (int j = 0; j < V; j++) {
      if (i != j) maxDist = max(maxDist, dist[i][j]);
    }
    if (maxDist < minMaxDist) {
      minMaxDist = maxDist;
      center = i;
    }
  }
  return center;
}

2. Count the Number of Shortest Paths

Modify the algorithm to also count how many different shortest paths exist between pairs.

int countPaths[V][V];
void floydWarshallCount(int dist[V][V]) {
  for (int i = 0; i < V; i++)
    for (int j = 0; j < V; j++)
      countPaths[i][j] = (dist[i][j] < INF);

  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];
          countPaths[i][j] = countPaths[i][k] * countPaths[k][j];
        } else if (dist[i][k] + dist[k][j] == dist[i][j]) {
          countPaths[i][j] += countPaths[i][k] * countPaths[k][j];
        }
      }
}

Hard Problem

Minimize the Longest Distance After Adding One Edge

Given a graph, compute the current longest shortest path, and evaluate where adding one edge reduces it the most.

int minimizeLongestDistance(int dist[V][V]) {
  int best = INF;
  for (int u = 0; u < V; u++) {
    for (int v = u + 1; v < V; v++) {
      if (dist[u][v] > 1) { // simulate adding an edge of weight 1
        int temp[V][V];
        memcpy(temp, dist, sizeof(temp));
        for (int i = 0; i < V; i++) {
          for (int j = 0; j < V; j++) {
            temp[i][j] = min(temp[i][j], min(temp[i][u] + 1 + temp[v][j], temp[i][v] + 1 + temp[u][j]));
          }
        }
        int maxDist = 0;
        for (int i = 0; i < V; i++)
          for (int j = 0; j < V; j++)
            maxDist = max(maxDist, temp[i][j]);
        best = min(best, maxDist);
      }
    }
  }
  return best;
}