Floyd-Warshall algorithm Using Python

 

The Floyd-Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles). It is capable of handling graphs with both directed and undirected edges, and it can compute the shortest path between every pair of nodes in the graph.

Here is an example of how you can implement the Floyd-Warshall algorithm in Python:

def floyd_warshall(graph):
    """
    Calculate the shortest path between all pairs of nodes in a graph using the Floyd-Warshall algorithm.

    Args:
    graph: a dictionary of dictionaries representing the graph, where the keys are the node labels and the values are dictionaries containing the neighbors of the node and their corresponding edge weights.

    Returns:
    A dictionary of dictionaries containing the shortest distance between all pairs of nodes and the path to get there.
    """

    # Initialize the distance and path dictionaries
    distance = {node: {node: 0 for node in graph} for node in graph}
    path = {node: {node: [node] for node in graph} for node in graph}

    # Iterate over all pairs of nodes
    for k in graph:
        for i in graph:
            for j in graph:
                # If the path from i to j through k is shorter than the current path, update the distance and path
                if distance[i][j] > distance[i][k] + distance[k][j]:
                    distance[i][j] = distance[i][k] + distance[k][j]
                    path[i][j] = path[i][k] + path[k][j][1:]

    return distance, path

# Example usage
graph = {
    'A': {'B': 3, 'C': 4, 'D': 7},
    'B': {'C': 1, 'D': 2},
    'C': {'D': 2},
    'D': {'C': 5}
}

distance, path = floyd_warshall(graph)
print(distance)
# Output: {'A': {'A': 0, 'B': 3, 'C': 4, 'D': 5},
#          'B': {'A': 3, 'B': 0, 'C': 1, 'D': 2},
#          'C': {'A': 4, 'B': 1, 'C': 0, 'D': 2},
#          'D': {'A': 5, 'B': 2, 'C': 2, 'D': 0}}
print(path)
# Output: {'A': {'A': ['A'], 'B': ['A', 'B'], 'C': ['A', 'C'], 'D': ['A', 'C', 'D']},
#          'B': {'A': ['B', 'A'], 'B': ['B'], 'C': ['B', 'C'], 'D': ['B', 'D']},
#          'C': {'A': ['C', 'A'], 'B': ['C', 'B'], 'C': ['C'], 'D': ['C', 'D']},
#          'D': {'A': ['D', 'C', 'A'], 'B': ['D', 'B'], 'C': ['D', 'C'], 'D': ['D']}}

The output of the algorithm is a dictionary of dictionaries `distance`, where `distance[i][j]` represents the shortest distance between nodes `i` and `j`, and a dictionary of dictionaries `path`, where `path[i][j]` represents the shortest path between nodes `i` and `j`.