Floyd–Warshall

"""Chapter 25 — Floyd-Warshall: Basic Implementation
Topic : Floyd-Warshall All-Pairs Shortest Path
Time  : O(V³)
Space : O(V²)

Description:
    Calculates all-pairs shortest paths using DP.
    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    Note that k (the intermediate node) is in the outermost loop."""

import sys

INF = float("inf")


def floyd_warshall(
    n: int,
    edges: list[tuple[int, int, int]],
    directed: bool = True,
) -> list[list[float]]:
    """Returns all-pairs shortest distances using Floyd-Warshall.

    Args:
        n       : Number of nodes (0-indexed: 0 ~ n-1)
        edges   : List of edges as (u, v, w)
        directed: True if the graph is directed

    Returns:
        dist[i][j]: Shortest distance from i to j (float('inf') if unreachable)

    Time : O(V³)
    Space: O(V²)"""
    #Initialization: INF, itself is 0
    dist: list[list[float]] = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0.0

    #Input edges
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], float(w))
        if not directed:
            dist[v][u] = min(dist[v][u], float(w))

    #Main loop — k (intermediate node) is the outermost!
    for k in range(n):
        for i in range(n):
            if dist[i][k] == INF:   #Early termination optimization
                continue
            for j in range(n):
                via_k = dist[i][k] + dist[k][j]
                if via_k < dist[i][j]:
                    dist[i][j] = via_k

    return dist


def print_dist_matrix(dist: list[list[float]], labels: list[str]) -> None:
    """Prints the distance matrix in a readable format."""
    n = len(labels)
    header = "     " + "".join(f"{lb:>8}" for lb in labels)
    print(header)
    print("     " + "-" * (8 * n))
    for i, row in enumerate(dist):
        cells = []
        for d in row:
            cells.append("INF" if d == INF else f"{int(d)}")
        print(f"  {labels[i]} |" + "".join(f"{c:>8}" for c in cells))


def main() -> None:
    #── Example 1: Lecture main graph ──
    print("=" * 60)
    print("Example 1: Directed graph (0~3)")
    print("=" * 60)
    edges1 = [
        (0, 1, 3),
        (0, 2, 2),
        (0, 3, 7),
        (1, 2, 1),
        (2, 3, 1),
    ]
    dist1 = floyd_warshall(4, edges1, directed=True)
    print_dist_matrix(dist1, ["0", "1", "2", "3"])

    print()
    print("Direct check (shortest 0→3):", int(dist1[0][3]))

    #── Example 2: Including negative edges ──
    print()
    print("=" * 60)
    print("Example 2: Including negative edges (no cycles)")
    print("=" * 60)
    edges2 = [
        (0, 1, 5),
        (1, 2, -3),
        (0, 2, 4),
        (2, 3, 2),
    ]
    dist2 = floyd_warshall(4, edges2, directed=True)
    print_dist_matrix(dist2, ["A", "B", "C", "D"])

    print()
    print("Shortest A→C:", int(dist2[0][2]), "(5 + (-3) = 2 vs direct 4 → choose 2)")

    #── Example 3: Undirected graph ──
    print()
    print("=" * 60)
    print("Example 3: Undirected graph")
    print("=" * 60)
    edges3 = [
        (0, 1, 1),
        (1, 2, 3),
        (0, 2, 10),
        (2, 3, 2),
    ]
    dist3 = floyd_warshall(4, edges3, directed=False)
    print_dist_matrix(dist3, ["P", "Q", "R", "S"])
    print()
    print("Shortest P→S:", int(dist3[0][3]), "(P→Q→R→S = 1+3+2 = 6)")

    #── Complexity summary ──
    print()
    print("=" * 60)
    print("Complexity summary")
    print("=" * 60)
    for v in [10, 100, 500, 1000]:
        ops = v ** 3
        print(f"V={v:>5}: O(V³) = {ops:>12,} operations"
              f"{'OK' if ops <= 1e8 else 'TLE risk'}")


if __name__ == "__main__":
    main()

"""Chapter 25 — Floyd-Warshall: Path Reconstruction (next matrix)
Topic : Floyd-Warshall with Path Reconstruction
Time  : O(V³) construction / O(V) path reconstruction
Space : O(V²)

Description:
    next[i][j] = the next node after i in the shortest path from i to j.
    Initialization: for directly connected edges (u,v) → next[u][v] = v
    Update: when dist[i][j] is updated, next[i][j] = next[i][k]
    Reconstruction: starting from i and following next[cur][j] gives the path."""

INF = float("inf")


def floyd_warshall_with_path(
    n: int,
    edges: list[tuple[int, int, int]],
    directed: bool = True,
) -> tuple[list[list[float]], list[list[int]]]:
    """Returns the Floyd-Warshall + path reconstruction matrices.

    Returns:
        (dist, nxt)
        dist[i][j]: shortest distance from i to j
        nxt[i][j]: next node after i on the shortest path to j (-1 if none)

    Time : O(V³)
    Space: O(V²)"""
    dist: list[list[float]] = [[INF] * n for _ in range(n)]
    nxt: list[list[int]] = [[-1] * n for _ in range(n)]

    #Initialization
    for i in range(n):
        dist[i][i] = 0.0

    for u, v, w in edges:
        if float(w) < dist[u][v]:
            dist[u][v] = float(w)
            nxt[u][v] = v
        if not directed and float(w) < dist[v][u]:
            dist[v][u] = float(w)
            nxt[v][u] = u

    #Main Loop
    for k in range(n):
        for i in range(n):
            if dist[i][k] == INF:
                continue
            for j in range(n):
                via_k = dist[i][k] + dist[k][j]
                if via_k < dist[i][j]:
                    dist[i][j] = via_k
                    nxt[i][j] = nxt[i][k]   #← Update Path

    return dist, nxt


def reconstruct_path(
    nxt: list[list[int]],
    src: int,
    dst: int,
) -> list[int]:
    """Reconstructs the shortest path from src → dst using the nxt matrix.

    Returns:
        List of path nodes (empty list if unreachable)

    Time : O(V)
    Space: O(V)"""
    if nxt[src][dst] == -1:
        return []
    path = [src]
    cur = src
    while cur != dst:
        cur = nxt[cur][dst]
        if cur == -1:
            return []   #Interrupted in the middle (Abnormal)
        path.append(cur)
    return path


def main() -> None:
    #── Example Graph ──
    #Nodes: 0=Seoul, 1=Daejeon, 2=Daegu, 3=Busan
    #Edges (Undirected)
    labels = ["Seoul", "Daejeon", "Daegu", "Busan"]
    edges = [
        (0, 1, 140),   #Seoul-Daejeon
        (1, 2, 120),   #Daejeon-Daegu
        (2, 3, 80),    #Daegu-Busan
        (0, 3, 450),   #Seoul-Busan (Direct)
        (1, 3, 200),   #Daejeon-Busan
    ]
    n = 4

    dist, nxt = floyd_warshall_with_path(n, edges, directed=False)

    print("=" * 60)
    print("Distance Matrix")
    print("=" * 60)
    header = "          " + "".join(f"{lb:>8}" for lb in labels)
    print(header)
    for i, row in enumerate(dist):
        cells = ["INF" if d == INF else str(int(d)) for d in row]
        print(f"  {labels[i]:>4} |" + "".join(f"{c:>8}" for c in cells))

    print()
    print("=" * 60)
    print("Path Reconstruction")
    print("=" * 60)
    for src in range(n):
        for dst in range(n):
            if src == dst:
                continue
            path = reconstruct_path(nxt, src, dst)
            if path:
                p_str = " → ".join(labels[p] for p in path)
                print(f"  {labels[src]} → {labels[dst]}: "
                      f"Distance={int(dist[src][dst])}km  Path={p_str}")

    print()
    print("=" * 60)
    print("Seoul → Busan Details")
    print("=" * 60)
    path_sb = reconstruct_path(nxt, 0, 3)
    p_str = " → ".join(labels[p] for p in path_sb)
    print(f"Path: {p_str}")
    print(f"Distance: {int(dist[0][3])} km")
    print(f"Direct (450) vs Via ({int(dist[0][3])}) →"
          f"{'Via is advantageous' if dist[0][3] < 450 else 'Direct is advantageous'}")


if __name__ == "__main__":
    main()

"""Chapter 25 — Floyd-Warshall: Negative Cycle Detection
Topic : Negative Cycle Detection via Floyd-Warshall
Time  : O(V³)
Space : O(V²)

Description:
    After running Floyd-Warshall, if there exists a node with dist[i][i] < 0,
    that node is on a negative cycle.

    Additionally: if dist[i][j] ≠ INF but dist[i][i] < 0 or
    dist[j][j] < 0, the shortest distance from i to j is -∞ (undefined)."""

INF = float("inf")


def floyd_warshall(
    n: int,
    edges: list[tuple[int, int, int]],
) -> list[list[float]]:
    """Basic Floyd-Warshall (directed graph). Time O(V³), Space O(V²)."""
    dist: list[list[float]] = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0.0
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], float(w))

    for k in range(n):
        for i in range(n):
            if dist[i][k] == INF:
                continue
            for j in range(n):
                via_k = dist[i][k] + dist[k][j]
                if via_k < dist[i][j]:
                    dist[i][j] = via_k

    return dist


def detect_negative_cycles(dist: list[list[float]]) -> list[int]:
    """Returns the list of nodes that belong to a negative cycle.

    Principle: If there is a negative cycle, for the node i in it, dist[i][i] < 0.

    Time : O(V)
    Space: O(V)"""
    return [i for i in range(len(dist)) if dist[i][i] < 0]


def is_reachable_through_neg_cycle(
    dist: list[list[float]],
    neg_nodes: list[int],
    src: int,
    dst: int,
) -> bool:
    """Checks whether the path from src → dst passes through a negative cycle.
    If it does, the shortest distance is -∞.

    Time : O(V)"""
    for k in neg_nodes:
        if dist[src][k] < INF and dist[k][dst] < INF:
            return True
    return False


def main() -> None:
    #── Case 1: No negative cycle ──
    print("=" * 60)
    print("Case 1: There are negative edges but no cycle")
    print("  0→1: 2,  1→2: -1,  0→2: 4")
    print("=" * 60)
    edges1 = [(0, 1, 2), (1, 2, -1), (0, 2, 4)]
    dist1 = floyd_warshall(3, edges1)
    neg1 = detect_negative_cycles(dist1)

    for i in range(3):
        print(f"  dist[{i}][{i}] = {dist1[i][i]}")
    print(f"Negative cycle nodes: {neg1 if neg1 else 'None'}")
    print(f"0→2 shortest: {int(dist1[0][2])} (0→1→2 = 2-1 = 1 < 4)")

    #── Case 2: Negative cycle exists ──
    print()
    print("=" * 60)
    print("Case 2: Negative cycle exists")
    print("0→1: 1,  1→2: -3,  2→1: 1  (cycle 1→2→1 = -3+1 = -2)")
    print("=" * 60)
    edges2 = [(0, 1, 1), (1, 2, -3), (2, 1, 1), (2, 3, 1)]
    dist2 = floyd_warshall(4, edges2)
    neg2 = detect_negative_cycles(dist2)

    for i in range(4):
        d = dist2[i][i]
        print(f"dist[{i}][{i}] = {d:.1f}  {'← Negative cycle!' if d < 0 else ''}")

    print(f"Negative cycle nodes: {neg2}")
    print(f"Does the 0→3 path pass through a negative cycle?:"
          f"{is_reachable_through_neg_cycle(dist2, neg2, 0, 3)}")
    print("→ 0→3 shortest distance is -∞ (does not converge)")

    #── Case 3: Practical use — branching depending on the presence of a negative cycle ──
    print()
    print("=" * 60)
    print("Case 3: Practical code pattern")
    print("=" * 60)
    edges3 = [(0, 1, 3), (1, 2, 2), (2, 0, -4)]  #0→1→2→0 = 1 (negative cycle)
    dist3 = floyd_warshall(3, edges3)
    neg3 = detect_negative_cycles(dist3)

    if neg3:
        print(f"Warning: Negative cycle detected (nodes {neg3})")
        print("Shortest path undefined — cycle handling required using Bellman-Ford, etc.")
    else:
        print("No negative cycle — Floyd-Warshall results are reliable")

    #── Summary ──
    print()
    print("=" * 60)
    print("Summary of negative cycle detection rules")
    print("=" * 60)
    print("After running Floyd-Warshall:")
    print("dist[i][i] < 0  →  Node i is on a negative cycle")
    print("If paths i→k and k→j both exist and k is on a negative cycle")
    print("→ i→j shortest = -∞")


if __name__ == "__main__":
    main()

"""Unit 25 — Floyd-Warshall: Transitive Closure
Topic: Transitive Closure (Reachability) via Floyd-Warshall
Time: O(V³) — can be optimized to O(V³/64) using bit operations
Space: O(V²)

Description:
    If reach[i][j] = True, j is reachable from i.
    Replace min(dist) in Floyd-Warshall with OR(reach).
    reach[i][j] |= (reach[i][k] and reach[k][j])
    Or using integer bitmask: reach[i] |= reach[k] if reach[i] >> k & 1"""


def transitive_closure_bool(
    n: int,
    edges: list[tuple[int, int]],
    directed: bool = True,
) -> list[list[bool]]:
    """Compute transitive closure using a boolean matrix.

    Time: O(V³)
    Space: O(V²)"""
    reach: list[list[bool]] = [[False] * n for _ in range(n)]

    #Reachable by oneself
    for i in range(n):
        reach[i][i] = True

    #Directly connected edge
    for u, v in edges:
        reach[u][v] = True
        if not directed:
            reach[v][u] = True

    #Floyd-Warshall (OR version)
    for k in range(n):
        for i in range(n):
            if not reach[i][k]:
                continue
            for j in range(n):
                if reach[k][j]:
                    reach[i][j] = True

    return reach


def transitive_closure_bitset(
    n: int,
    edges: list[tuple[int, int]],
    directed: bool = True,
) -> list[int]:
    """Compute transitive closure using integer bitmasks.
    If the j-th bit of reach[i] is 1, i→j is reachable.

    Time: O(V³ / 64)  (using integer bit operations)
    Space: O(V²/64) → effectively an O(V) list of integers"""
    reach = [0] * n

    #Oneself
    for i in range(n):
        reach[i] |= (1 << i)

    #Directly connected
    for u, v in edges:
        reach[u] |= (1 << v)
        if not directed:
            reach[v] |= (1 << u)

    #Floyd (bit OR)
    for k in range(n):
        for i in range(n):
            if reach[i] >> k & 1:    #Reachable i → k
                reach[i] |= reach[k] #All neighbors of i → k reachable

    return reach


def print_reach_matrix(reach: list[list[bool]], labels: list[str]) -> None:
    """Output the reachability matrix."""
    n = len(labels)
    header = "      " + "".join(f"{lb:>5}" for lb in labels)
    print(header)
    print("      " + "─" * (5 * n))
    for i, row in enumerate(reach):
        cells = ["O" if r else "X" for r in row]
        print(f"  {labels[i]:>3} |" + "".join(f"{c:>5}" for c in cells))


def main() -> None:
    #── Example 1: Directed Graph ──
    print("=" * 55)
    print("Example 1: Directed Graph Transitive Closure")
    print("0→1, 1→2, 2→3, 3→0  (Cycle)")
    print("=" * 55)

    edges1 = [(0, 1), (1, 2), (2, 3), (3, 0)]
    n = 4
    labels = ["0", "1", "2", "3"]

    reach_bool = transitive_closure_bool(n, edges1)
    print_reach_matrix(reach_bool, labels)

    reach_bits = transitive_closure_bitset(n, edges1)
    print()
    print("Bitmask result (same content):")
    for i in range(n):
        reachable = [j for j in range(n) if reach_bits[i] >> j & 1]
        print(f"Reachable from {i}: {reachable}")

    #── Example 2: DAG (No cycles) ──
    print()
    print("=" * 55)
    print("Example 2: DAG — Course prerequisite relationships")
    print("Math→Physics→Chemistry, Math→Statistics→AI, Physics→AI")
    print("=" * 55)

    subjects = ["Mathematics", "Physics", "Chemistry", "Statistics", "AI"]
    edges2 = [(0, 1), (1, 2), (0, 3), (3, 4), (1, 4)]
    reach2 = transitive_closure_bool(5, edges2)
    print_reach_matrix(reach2, ["Mathematics", "Physics", "Chemistry", "Statistics", "AI"])

    print()
    print("Courses available if you know 'Math':")
    can_take = [subjects[j] for j in range(5) if reach2[0][j] and j != 0]
    print(f"  {can_take}")

    #── Example 3: Baekjoon 11403 type ──
    print()
    print("=" * 55)
    print("Example 3: Baekjoon 11403 style — 0-indexed adjacency matrix input")
    print("=" * 55)
    adj = [
        [0, 1, 0, 0],
        [0, 0, 0, 1],
        [0, 0, 0, 0],
        [0, 0, 0, 0],
    ]
    edges3 = [(i, j) for i in range(4) for j in range(4) if adj[i][j]]
    reach3 = transitive_closure_bool(4, edges3)

    print("Input adj:")
    for row in adj:
        print(f"  {row}")
    print("Output reach (O=1, X=0):")
    for row in reach3:
        print(f"  {[1 if r else 0 for r in row]}")


if __name__ == "__main__":
    main()