bhylu.com

Advertisements

DSA Floyd-Warshall Algorithm

Floyd–Warshall considers which intermediate vertices a route may use. It is useful when many pair distances are needed and the graph is small enough for a full distance table.

How it works

The middle-vertex loop belongs outside the source and target loops. After each middle choice, distances may use the processed set of intermediate vertices. Zero on the diagonal represents an empty route, not a missing self-edge; repeated direct edges use the smallest available weight. This implementation rejects a negative cycle anywhere because its contract asks for finite all-pairs answers. It returns distances only, not reconstructed routes.

Run the code

Select Try in playground to load this complete source into the existing Python editor. It does not run automatically; choose Run when ready. These examples use only the Python standard library and small fictional inputs. They do not need database services, extra packages or personal files.

For local work, save the complete source as all-pairs.py and run python all-pairs.py. The local review uses Python 3.12.14; the browser uses the existing Pyodide 0.27.7 runtime. Keep inputs small, respect explicit table/tour budgets and account for recursion limits before increasing a fixture’s size.

Example

all-pairs.py
Try in playground

def validate_graph(graph, weighted=False, nonnegative=False):
    if not isinstance(graph, dict):
        raise ValueError("Expected an adjacency dictionary")
    if any(not isinstance(vertex, str) for vertex in graph):
        raise ValueError("String vertex labels required")
    for vertex, neighbors in graph.items():
        for edge in neighbors:
            if weighted:
                target, weight = edge
                if type(weight) is not int or (nonnegative and weight < 0):
                    raise ValueError("Invalid integer edge weight")
            else:
                target = edge
            if target not in graph:
                raise ValueError("Unknown target vertex")

def all_pairs(graph):
    validate_graph(graph, weighted=True)
    vertices = list(graph)
    distance = {source: {target: float("inf") for target in vertices} for source in vertices}
    for vertex in vertices:
        distance[vertex][vertex] = 0
        for target, weight in graph[vertex]:
            distance[vertex][target] = min(distance[vertex][target], weight)
    for middle in vertices:
        for source in vertices:
            for target in vertices:
                distance[source][target] = min(distance[source][target], distance[source][middle] + distance[middle][target])
    if any(distance[vertex][vertex] < 0 for vertex in vertices):
        raise ValueError("Negative cycle prevents finite all-pairs distances")
    return distance

distance = all_pairs({"gate": [("oak", 4), ("pond", 1)], "oak": [("shed", 1)], "pond": [("oak", 2), ("shed", 7)], "shed": [], "hill": []})
print(distance["gate"]["shed"])
print(distance["hill"]["gate"])
print(distance["oak"]["oak"])

Expected result

4
inf
0

Gate-to-shed agrees with the single-source result, hill remains disconnected and an empty oak-to-oak route costs zero. The independent property review compares small-graph results across methods instead of trusting one table fixture.

Time, space and assumptions

Time is O(V³) and distance storage O(V²). The cubic algorithm may be inappropriate for a large sparse graph even when each individual table entry is easy to access.

Consult the Python 3.12 standard-library reference for container and language contracts; an example result is not a proof of every possible input or real-world performance.

Advertisements