Floyd-Warshall

The Floyd-Warshall algorithm is a dynamic programming algorithm used to find the shortest paths between all pairs of vertices in a weighted graph.

It works for both directed and undirected graphs with positive or negative edge weights (but with no negative cycles).

Here's a simple explanation of the Floyd-Warshall algorithm:

1. Initialization: Create a distance matrix dist where dist[i][j] represents the shortest distance from vertex i to vertex j. Initialize this matrix with the direct edge weights if there is an edge between i and j, otherwise, initialize it with a very large value to represent infinity. Also, initialize the diagonal elements to 0 because the shortest distance from a vertex to itself is always 0.

2. Main Algorithm: Iterate over all vertices k, and consider all pairs of vertices (i, j). For each pair (i, j), if vertex k is on the shortest path from i to j, then update the value of dist[i][j] to dist[i][k] + dist[k][j] if it's smaller than the current value of dist[i][j].

3. Final Result: After completing the iterations, the dist matrix will contain the shortest distances between all pairs of vertices.

pseudocode:

procedure FloydWarshall (graph[][], int vertices)
    let dist[][] be a matrix of size vertices × vertices
    
    // Initialize distances
    for each i = 1 to vertices
        for each j = 1 to vertices
            dist[i][j] = graph[i][j]
    
    // Update distances using intermediate vertices
    for each k = 1 to vertices
        for each i = 1 to vertices
            for each j = 1 to vertices
                if dist[i][k] + dist[k][j] < dist[i][j]
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    // Print the shortest distances
    for each i = 1 to vertices
        for each j = 1 to vertices
            print dist[i][j]

function floydWarshall(graph) {
    const numVertices = graph.length;
    let dist = [];
    
    // Step 1: Initialize the distance matrix
    for (let i = 0; i < numVertices; i++) {
        dist[i] = [];
        for (let j = 0; j < numVertices; j++) {
            if (i === j) {
                dist[i][j] = 0;  // Distance from a vertex to itself is 0
            } else if (graph[i][j] !== undefined) {
                dist[i][j] = graph[i][j];  // Direct edge weight
            } else {
                dist[i][j] = Infinity;  // No direct edge, set distance to infinity
            }
        }
    }

    // Step 2: Main algorithm
    for (let k = 0; k < numVertices; k++) {
        for (let i = 0; i < numVertices; i++) {
            for (let j = 0; j < numVertices; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // Step 3: Return the shortest distances
    return dist;
}

// Example graph represented as an adjacency matrix
const graph = [
    [0, 3, undefined, 7],
    [8, 0, 2, undefined],
    [5, undefined, 0, 1],
    [2, undefined, undefined, 0]
];

console.log(floydWarshall(graph));

In this example, graph represents a directed graph with 4 vertices. undefined values indicate that there's no direct edge between those vertices.

The function floydWarshall() returns the shortest distances between all pairs of vertices in the graph.