The Floyd-Warshall algorithm solves the all-pairs shortest path problem in a weighted graph, handling both positive and negative edge weights (with no negative cycles). It uses dynamic programming to iteratively improve shortest path estimates between every pair of vertices.

Core Principal

Define dist[i][j][k] as the shortest distance from node i to node j using only vertices from the set {0, 1, ..., k-1} as intermediate points. The recurrence relation is:

dist[i][j][k] = min(dist[i][j][k-1], dist[i][k][k-1] + dist[k][j][k-1])

• If the shortest path from i to j does not pass through node k, the dsitance remains dist[i][j][k-1].
• If it does pass through k, the distance is the sum of the shortest path from i to k and from k to j using only earlier vertices as intermediates.

Implementation Example

The following code converts an edge-list graph to an adjacency matrix, runs the Floyd-Warshall algorithm, and tracks the next vertex in shortest path for reconstruction.

from collections import defaultdict

def build_weighted_graph():
    """Initialize a sample weighted directed graph"""
    return {
        'X': [('X', 'Y', 2)],
        'Y': [('Y', 'Z', 1), ('Y', 'W', 6)],
        'Z': [('Z', 'X', 5), ('Z', 'W', 4)],
        'W': [('W', 'X', 3)]
    }

def convert_to_matrix(graph):
    """Transform edge list to adjacency matrix representation"""
    nodes = sorted(graph.keys())
    node_count = len(nodes)
    idx_map = {node: i for i, node in enumerate(nodes)}
    
    # Initialize matrix with 0 on diagonal, infinity elsewhere
    matrix = [[float('inf')] * node_count for _ in range(node_count)]
    for i in range(node_count):
        matrix[i][i] = 0
    
    for src, edges in graph.items():
        src_idx = idx_map[src]
        for edge in edges:
            _, dest, weight = edge
            dest_idx = idx_map[dest]
            matrix[src_idx][dest_idx] = weight
    return matrix, nodes

def compute_all_pairs_shortest_paths(adj_mat):
    """Run Floyd-Warshall algorithm on adjacency matrix"""
    num_nodes = len(adj_mat)
    # Copy initial distances
    dist = [row[:] for row in adj_mat]
    # Track next node in shortest path for path reconstruction
    next_node = [[-1] * num_nodes for _ in range(num_nodes)]
    
    for i in range(num_nodes):
        for j in range(num_nodes):
            if adj_mat[i][j] != float('inf') or i == j:
                next_node[i][j] = j
    
    # Relax paths through intermediate node k
    for k in range(num_nodes):
        for i in range(num_nodes):
            for j in range(num_nodes):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    next_node[i][j] = next_node[i][k]
    return dist, next_node

# Execution
graph_data = build_weighted_graph()
adj_matrix, node_list = convert_to_matrix(graph_data)
final_dist, path_next = compute_all_pairs_shortest_paths(adj_matrix)

# Print initial adjacency matrix
print("Initial Adjacency Matrix:")
for row in adj_matrix:
    print('\t'.join(str(x) for x in row))
print('-' * 50)

# Print next node matrix
print("Next Node Matrix (for path reconstruction):")
for row in path_next:
    print('\t'.join(str(x) for x in row))
print('-' * 50)

# Print final shortest distances
print("Final Shortest Distances:")
for row in final_dist:
    print('\t'.join(str(x) for x in row))

Optimized Variant

The standard implementation can be optimized with early termination checks to skip unnecessary computations:

1. Skip relaxation if either dist[i][k] or dist[k][j] is infinity (no path exists through k).
2. Skip self-iteration (i == k or k == j) since intermediate nodes cannot be the source or destination for that iteration.
3. Only perform the addition and comparison if dist[i][k] and dist[k][j] are both smaller than the current dist[i][j], reducing unnecessary arithmetic.

def optimized_floyd_warshall(adj_mat):
    """Floyd-Warshall with early skip optimizations"""
    num_nodes = len(adj_mat)
    dist = [row[:] for row in adj_mat]
    next_node = [[-1] * num_nodes for _ in range(num_nodes)]
    
    for i in range(num_nodes):
        for j in range(num_nodes):
            if adj_mat[i][j] != float('inf') or i == j:
                next_node[i][j] = j
    
    for k in range(num_nodes):
        for i in range(num_nodes):
            # Skip if i equals k (no intermediate) or no path from i to k
            if i == k or dist[i][k] == float('inf'):
                continue
            for j in range(num_nodes):
                # Skip if j equals k or no path from k to j
                if j == k or dist[k][j] == float('inf'):
                    continue
                # Only compute sum if both segments are shorter than current distance
                if dist[i][k] < dist[i][j] and dist[k][j] < dist[i][j]:
                    candidate = dist[i][k] + dist[k][j]
                    if candidate < dist[i][j]:
                        dist[i][j] = candidate
                        next_node[i][j] = next_node[i][k]
    return dist, next_node