Floyd-Warshall Algorithm

def floyd_warshall(n, edges):
    """
    Find shortest paths between all pairs of vertices
    n: number of vertices (0-indexed)
    edges: list of (u, v, weight)
    Returns: distance matrix
    """
    # Initialize distance matrix
    dist = [[float('inf')] * n for _ in range(n)]

    # Distance from vertex to itself is 0
    for i in range(n):
        dist[i][i] = 0

    # Add edges
    for u, v, w in edges:
        dist[u][v] = w
        # For undirected graph, add reverse edge:
        # dist[v][u] = w

    # Floyd-Warshall: try all intermediate vertices
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

def floyd_warshall_with_path(n, edges):
    """
    Find shortest paths and reconstruct actual paths
    Returns: (distance matrix, next vertex matrix)
    """
    dist = [[float('inf')] * n for _ in range(n)]
    next_vertex = [[None] * n for _ in range(n)]

    # Initialize
    for i in range(n):
        dist[i][i] = 0
        next_vertex[i][i] = i

    for u, v, w in edges:
        dist[u][v] = w
        next_vertex[u][v] = v

    # Floyd-Warshall
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    next_vertex[i][j] = next_vertex[i][k]

    return dist, next_vertex

def reconstruct_path(next_vertex, u, v):
    """Reconstruct path from u to v"""
    if next_vertex[u][v] is None:
        return []

    path = [u]
    while u != v:
        u = next_vertex[u][v]
        path.append(u)
    return path

def transitive_closure(n, edges):
    """
    Determine if there's a path between every pair of vertices
    Returns: boolean reachability matrix
    """
    reach = [[False] * n for _ in range(n)]

    # Initialize: vertex can reach itself
    for i in range(n):
        reach[i][i] = True

    # Mark direct edges
    for u, v in edges:
        reach[u][v] = True

    # Floyd-Warshall for reachability
    for k in range(n):
        for i in range(n):
            for j in range(n):
                reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])

    return reach

def detect_negative_cycle(n, edges):
    """
    Detect if graph contains negative cycle
    Returns: (has_negative_cycle, distance_matrix)
    """
    dist = [[float('inf')] * n for _ in range(n)]

    for i in range(n):
        dist[i][i] = 0

    for u, v, w in edges:
        dist[u][v] = w

    # Floyd-Warshall
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    # Check diagonal for negative values
    has_negative_cycle = any(dist[i][i] < 0 for i in range(n))

    return has_negative_cycle, dist

def floyd_warshall_minimax(n, edges):
    """
    Find path that minimizes the maximum edge weight
    Useful for capacity/bandwidth problems
    """
    # Initialize with infinity (no path)
    dist = [[float('inf')] * n for _ in range(n)]

    for i in range(n):
        dist[i][i] = 0

    for u, v, w in edges:
        dist[u][v] = w

    # Floyd-Warshall with minimax operation
    for k in range(n):
        for i in range(n):
            for j in range(n):
                # Minimize the maximum edge on path
                dist[i][j] = min(dist[i][j], max(dist[i][k], dist[k][j]))

    return dist

def floyd_warshall_optimized(n, edges):
    """
    Space-optimized: use single matrix (in-place update)
    """
    dist = [[float('inf')] * n for _ in range(n)]

    for i in range(n):
        dist[i][i] = 0

    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)  # Handle multiple edges

    # In-place updates are safe due to intermediate vertex property
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    return dist

Algorithm Selection Flowchart:

1. Need all-pairs shortest paths?
   ├── YES → Consider Floyd-Warshall
   │   ├── Small graph (V ≤ 400)? → Use Floyd-Warshall
   │   └── Large graph? → Run Dijkstra/Bellman-Ford V times
   └── NO → Single-source problem → Continue to 2

2. Are there negative edge weights?
   ├── YES → Use Bellman-Ford (or SPFA)
   └── NO → Use Dijkstra

3. Is graph dense (E ≈ V²)?
   ├── YES → Consider Floyd-Warshall for all-pairs
   └── NO → Dijkstra is more efficient

// LC 1334 - Find the City With the Smallest Number of Neighbors at a Threshold Distance
// IDEA: Floyd-Warshall all-pairs shortest path; count reachable per city within threshold
// time = O(N^3), space = O(N^2)
public int findTheCity(int n, int[][] edges, int distanceThreshold) {
    int[][] dist = new int[n][n];
    for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE / 2);
    for (int i = 0; i < n; i++) dist[i][i] = 0;
    for (int[] e : edges) { dist[e[0]][e[1]] = e[2]; dist[e[1]][e[0]] = e[2]; }
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
    int ans = -1, minCount = n;
    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = 0; j < n; j++) if (i != j && dist[i][j] <= distanceThreshold) count++;
        if (count <= minCount) { minCount = count; ans = i; }
    }
    return ans;
}

# LC 1334 - Find the City With the Smallest Number of Neighbors at a Threshold Distance
# Classic Floyd-Warshall application

def findTheCity(n, edges, distanceThreshold):
    """
    Find city with smallest number of reachable cities within threshold
    """
    # Initialize distance matrix
    dist = [[float('inf')] * n for _ in range(n)]

    for i in range(n):
        dist[i][i] = 0

    for u, v, w in edges:
        dist[u][v] = w
        dist[v][u] = w  # Undirected graph

    # Floyd-Warshall
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    # Count reachable cities for each city
    min_reachable = float('inf')
    result_city = -1

    for i in range(n):
        reachable = sum(1 for j in range(n) if i != j and dist[i][j] <= distanceThreshold)
        if reachable <= min_reachable:
            min_reachable = reachable
            result_city = i

    return result_city

// LC 1462 - Course Schedule IV
// IDEA: Floyd-Warshall transitive closure; reachable[i][j] = i is prerequisite of j
// time = O(N^3), space = O(N^2)
public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
    boolean[][] reach = new boolean[numCourses][numCourses];
    for (int[] p : prerequisites) reach[p[0]][p[1]] = true;
    for (int k = 0; k < numCourses; k++)
        for (int i = 0; i < numCourses; i++)
            for (int j = 0; j < numCourses; j++)
                if (reach[i][k] && reach[k][j]) reach[i][j] = true;
    List<Boolean> ans = new ArrayList<>();
    for (int[] q : queries) ans.add(reach[q[0]][q[1]]);
    return ans;
}

# LC 1462 - Course Schedule IV
# Transitive closure problem

def checkIfPrerequisite(numCourses, prerequisites, queries):
    """
    Determine if course A is a prerequisite of course B (direct or indirect)
    """
    n = numCourses
    # is_prereq[i][j] = True if i is prerequisite of j
    is_prereq = [[False] * n for _ in range(n)]

    # Mark direct prerequisites
    for pre, course in prerequisites:
        is_prereq[pre][course] = True

    # Floyd-Warshall for transitive closure
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if is_prereq[i][k] and is_prereq[k][j]:
                    is_prereq[i][j] = True

    # Answer queries
    return [is_prereq[u][v] for u, v in queries]

// LC 743 - Network Delay Time (Floyd-Warshall approach)
// IDEA: All-pairs Floyd-Warshall; answer = max dist[k-1][i] for all i
// time = O(N^3), space = O(N^2)
public int networkDelayTime(int[][] times, int n, int k) {
    int[][] dist = new int[n][n];
    for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE / 2);
    for (int i = 0; i < n; i++) dist[i][i] = 0;
    for (int[] t : times) dist[t[0]-1][t[1]-1] = t[2];
    for (int mid = 0; mid < n; mid++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                dist[i][j] = Math.min(dist[i][j], dist[i][mid] + dist[mid][j]);
    int max = 0;
    for (int i = 0; i < n; i++) {
        if (dist[k-1][i] == Integer.MAX_VALUE / 2) return -1;
        max = Math.max(max, dist[k-1][i]);
    }
    return max;
}

# LC 743 - Network Delay Time
# Can use Floyd-Warshall but Dijkstra is more efficient

def networkDelayTime(times, n, k):
    """
    Floyd-Warshall approach (overkill for single-source)
    """
    dist = [[float('inf')] * n for _ in range(n)]

    for i in range(n):
        dist[i][i] = 0

    for u, v, w in times:
        dist[u-1][v-1] = w  # Convert to 0-indexed

    # Floyd-Warshall
    for mid in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][mid] + dist[mid][j])

    # Find max distance from source k-1
    k_idx = k - 1
    max_dist = max(dist[k_idx])

    return max_dist if max_dist != float('inf') else -1

// LC 1627 - Graph Connectivity With Threshold
// IDEA: Connect multiples of each gcd > threshold; Floyd-Warshall for connectivity queries
// time = O(N^2 log N + N^3 + Q), space = O(N^2)
public List<Boolean> areConnected(int n, int threshold, int[][] queries) {
    boolean[][] conn = new boolean[n + 1][n + 1];
    for (int i = 0; i <= n; i++) conn[i][i] = true;
    for (int g = threshold + 1; g <= n; g++)
        for (int mul = 2 * g; mul <= n; mul += g)
            conn[g][mul] = conn[mul][g] = true;
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (conn[i][k] && conn[k][j]) conn[i][j] = true;
    List<Boolean> ans = new ArrayList<>();
    for (int[] q : queries) ans.add(conn[q[0]][q[1]]);
    return ans;
}

# LC 1627 - Graph Connectivity With Threshold
# Union-Find is better, but Floyd-Warshall works

def areConnected(n, threshold, queries):
    """
    Determine if cities are connected via intermediate cities > threshold
    """
    # Build graph: cities connected if gcd > threshold
    edges = []
    for gcd_val in range(threshold + 1, n + 1):
        # All multiples of gcd_val are connected
        multiples = list(range(gcd_val, n + 1, gcd_val))
        for i in range(len(multiples) - 1):
            edges.append((multiples[i], multiples[i + 1]))

    # Floyd-Warshall for connectivity
    connected = [[False] * (n + 1) for _ in range(n + 1)]

    for i in range(n + 1):
        connected[i][i] = True

    for u, v in edges:
        connected[u][v] = connected[v][u] = True

    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if connected[i][k] and connected[k][j]:
                    connected[i][j] = True

    return [connected[u][v] for u, v in queries]

// LC 847 - Shortest Path Visiting All Nodes
// IDEA: BFS with bitmask state (node, visited); all nodes are valid starts
// time = O(2^N * N), space = O(2^N * N)
public int shortestPathLength(int[][] graph) {
    int n = graph.length, full = (1 << n) - 1;
    Queue<int[]> q = new LinkedList<>();
    boolean[][] visited = new boolean[n][1 << n];
    for (int i = 0; i < n; i++) { q.offer(new int[]{i, 1 << i, 0}); visited[i][1 << i] = true; }
    while (!q.isEmpty()) {
        int[] cur = q.poll();
        int node = cur[0], mask = cur[1], dist = cur[2];
        if (mask == full) return dist;
        for (int next : graph[node]) {
            int nextMask = mask | (1 << next);
            if (!visited[next][nextMask]) { visited[next][nextMask] = true; q.offer(new int[]{next, nextMask, dist + 1}); }
        }
    }
    return -1;
}

# LC 847 - Shortest Path Visiting All Nodes
# Use BFS with bitmask, but Floyd-Warshall for preprocessing

def shortestPathLength(graph):
    """
    Floyd-Warshall to precompute all-pairs distances,
    then use DP/BFS to find shortest path visiting all nodes
    """
    n = len(graph)

    # Build distance matrix using Floyd-Warshall
    dist = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
        for j in graph[i]:
            dist[i][j] = 1

    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    # Now use BFS with bitmask (actual solution)
    # ... (rest of solution uses dist matrix)

    # Simplified return for template
    return 0

// LC 787 - Cheapest Flights Within K Stops
// IDEA: min-plus matrix power. M[i][i]=0 makes "exactly t edges" into "at most t edges",
//       so answer = (M ^ (K+1))[src][dst]. Note k is the INNER loop here, unlike Floyd-Warshall.
// time = O(V^3 log K), space = O(V^2)
static final int INF = Integer.MAX_VALUE / 3;   // /3 so INF + INF never overflows

// C[i][j] = min over k of (A[i][k] + B[k][j])
private int[][] minPlus(int[][] A, int[][] B) {
    int n = A.length;
    int[][] C = new int[n][n];
    for (int[] row : C) Arrays.fill(row, INF);
    for (int i = 0; i < n; i++)
        for (int k = 0; k < n; k++) {          // k is INNER, not outer -> counts edges, not vertices
            if (A[i][k] >= INF) continue;      // prune: no route i -> k yet
            for (int j = 0; j < n; j++)
                C[i][j] = Math.min(C[i][j], A[i][k] + B[k][j]);
        }
    return C;
}

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    // M = one-flight cost matrix; diagonal 0 == "take fewer flights than allowed"
    int[][] M = new int[n][n];
    for (int[] row : M) Arrays.fill(row, INF);
    for (int i = 0; i < n; i++) M[i][i] = 0;
    for (int[] f : flights) M[f[0]][f[1]] = Math.min(M[f[0]][f[1]], f[2]);

    // res = identity of the min-plus semiring (0 on diagonal, INF elsewhere)
    int[][] res = new int[n][n];
    for (int i = 0; i < n; i++) { Arrays.fill(res[i], INF); res[i][i] = 0; }

    int e = k + 1;                              // K stops == K+1 flights
    while (e > 0) {
        if ((e & 1) == 1) res = minPlus(res, M);
        M = minPlus(M, M);
        e >>= 1;
    }
    return res[src][dst] >= INF ? -1 : res[src][dst];
}

# LC 787 - Cheapest Flights Within K Stops
# IDEA: min-plus matrix power. M[i][i]=0 makes "exactly t edges" into "at most t edges",
#       so answer = (M ** (K+1))[src][dst]. Note k is the INNER loop here, unlike Floyd-Warshall.
# time = O(V^3 log K), space = O(V^2)
INF = float('inf')

def min_plus(A, B, n):
    """C[i][j] = min over k of (A[i][k] + B[k][j])  -- (min, +) instead of (+, *)"""
    C = [[INF] * n for _ in range(n)]
    for i in range(n):
        Ai, Ci = A[i], C[i]
        for k in range(n):              # k is INNER, not outer -> counts edges, not vertices
            a = Ai[k]
            if a == INF:                # prune: no route i -> k yet
                continue
            Bk = B[k]
            for j in range(n):
                if a + Bk[j] < Ci[j]:
                    Ci[j] = a + Bk[j]
    return C

def findCheapestPrice(n, flights, src, dst, k):
    # M = one-flight cost matrix; diagonal 0 == "take fewer flights than allowed"
    M = [[INF] * n for _ in range(n)]
    for i in range(n):
        M[i][i] = 0
    for u, v, w in flights:
        M[u][v] = min(M[u][v], w)

    # res = identity of the min-plus semiring (0 on diagonal, INF elsewhere)
    res = [[0 if i == j else INF for j in range(n)] for i in range(n)]

    e = k + 1                            # K stops == K+1 flights
    while e:
        if e & 1:
            res = min_plus(res, M, n)
        M = min_plus(M, M, n)
        e >>= 1

    return -1 if res[src][dst] == INF else res[src][dst]

# Floyd-Warshall Implementation Checklist:

# 1. Initialize distance matrix
dist = [[float('inf')] * n for _ in range(n)]
for i in range(n): dist[i][i] = 0

# 2. Add edges
for u, v, w in edges: dist[u][v] = w

# 3. Three nested loops (ORDER MATTERS: k must be outer)
for k in range(n):           # Intermediate vertex
    for i in range(n):       # Source
        for j in range(n):   # Destination
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

# 4. Check for negative cycles (optional)
has_neg_cycle = any(dist[i][i] < 0 for i in range(n))

# 5. Handle disconnected components
# dist[i][j] == float('inf') means no path

# Pattern 1: Basic shortest path
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

# Pattern 2: Transitive closure (reachability)
reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])

# Pattern 3: Minimax (bottleneck)
dist[i][j] = min(dist[i][j], max(dist[i][k], dist[k][j]))

# Pattern 4: Maximum capacity
capacity[i][j] = max(capacity[i][j], min(capacity[i][k], capacity[k][j]))

# Pattern 5: Negative cycle detection
has_neg_cycle = any(dist[i][i] < 0 for i in range(n))