Floyd-Warshall Algorithm

Definition

Definition

The Floyd-Warshall algorithm is a dynamic programming technique used to find the shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles). It efficiently computes the shortest paths between all pairs of vertices in a graph, making it suitable for problems where the shortest distances between all pairs of vertices are required

Explanation

Initialize a distance matrix, which encapsulates the shortest distances between every pair of vertices within the graph. It then systematically iterates through the vertices, entertaining each vertex as a potential intermediary in pathfinding. During each iteration, the algorithm evaluates if including an intermediate vertex could potentially yield a shorter distance between two vertices. If such an improvement is discovered, the distance matrix is promptly updated. This process continues iteratively until the algorithm has thoroughly explored all possible paths, resulting in the determination of the shortest path between every pair of vertices within the graph

Guidance

• Initialize a distance matrix where each element represents the direct edge weight between vertices. If there's no direct edge, set the distance to infinity
• Iterate through all vertices and consider each vertex as an intermediate vertex in the shortest path computation
• For each pair of vertices (u, v), update the distance matrix by comparing the distance between u and v with the sum of distances between u and the intermediate vertex k and between the intermediate vertex k and v. If this sum is smaller, update the distance matrix accordingly
  • Repeat the step for all possible intermediate vertices
• After completing all iterations, the distance matrix will contain the shortest distances between all pairs of vertices

Tips

• ensure that the graph does not contain negative cycles, as the algorithm does not work correctly in such cases
• the algorithm can efficiently handle graphs with both positive and negative edge weights
• it is suitable for dense graphs or graphs with a relatively small number of vertices and edges

Practice

Practice

FloydWarshall(graph):
  n = number of vertices in the graph
  distance[][] = initialize distance matrix with direct edge weights

  // Compute shortest paths
  for k from 1 to n:
    for i from 1 to n:
      for j from 1 to n:
        // If vertex k is on the shortest path from i to j
        if distance[i][k] + distance[k][j] < distance[i][j]:
          distance[i][j] = distance[i][k] + distance[k][j]

  return distance

Solution

package main

func floydWarshall(graph [][]int, V int) [][]int {
	dist := make([][]int, V)

	for i := range dist {
		dist[i] = make([]int, V)
		copy(dist[i], graph[i])
	}

	for k := 0; k < V; k++ {
		for i := 0; i < V; i++ {
			for 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
}

import java.util.Arrays;

class FloydWarshall {

  final static int INF = 99999;

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

const INF = 99999;

function floydWarshall(graph) {
  const dist = [...graph.map((row) => [...row])];
  const V = dist.length;

  for (let k = 0; k < V; k++) {
    for (let i = 0; i < V; i++) {
      for (let 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;
}

fun floydWarshall(graph: Array<IntArray>, V: Int): Array<IntArray> {
    val dist = Array(V) { i -> IntArray(V) { j -> graph[i][j] } }

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

    return dist
}

INF = 99999

def floydWarshall(graph):
    V = len(graph)
    dist = [[0] * 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):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    return dist

const INF: i32 = 99999;

fn floyd_warshall(graph: &mut Vec<Vec<i32>>) {
    let V = graph.len();
    for k in 0..V {
        for i in 0..V {
            for j in 0..V {
                if graph[i][k] + graph[k][j] < graph[i][j] {
                    graph[i][j] = graph[i][k] + graph[k][j];
                }
            }
        }
    }
}

function floydWarshall(graph: number[][]): number[][] {
  const V = graph.length;
  const dist: number[][] = [];

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

  for (let k = 0; k < V; k++) {
    for (let i = 0; i < V; i++) {
      for (let 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;
}