Floyd Warshall Algorithm
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.graphs;
/* * ============================================================================================ * PROBLEM: Floyd Warshall Algorithm (All-Pairs Shortest Path) * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * Given an adjacency matrix A where A[i][j] is the weight of a directed edge from i to j. * - A[i][j] = 0 if i == j. * - A[i][j] = -1 if no edge exists. * Find the shortest path between every pair of vertices (i, j). * * --------------------- * 2. Logical Breakdown & Mathematical Formulation * --------------------- * Floyd-Warshall is a Dynamic Programming algorithm. We define dp[k][i][j] as the * shortest path from i to j using only vertices from the set {1, 2, ..., k} as * intermediate points. * * Recurrence Relation: * For each vertex k (acting as an intermediate bridge): * $\(dp[k][i][j] = \min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])\)$ * * Step-by-Step Implementation: * 1. Preprocessing: * - Replace all -1 values with a large "Infinity" value to facilitate Math.min(). * - Ensure A[i][j] = 0 for all i == j. * 2. Triple Nested Loops: * - The outer loop must be the intermediate vertex 'k'. * - The inner loops iterate through all pairs (i, j). * - Update: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). * 3. Post-processing: * - Convert any remaining "Infinity" values back to -1, indicating no path exists. * * --------------------- * 3. Constraints & Complexity Analysis * --------------------- * Time Complexity: O(N^3) * - Three nested loops each running N times. * Space Complexity: O(1) if we modify the input matrix in place, or O(N^2) for result. * * --------------------- * 4. Special Note on Negative Cycles * --------------------- * If after the algorithm dist[i][i] becomes less than 0 for any vertex i, the * graph contains a negative cycle. * ============================================================================================ / public class FloydWarshallAlgorithm { public int[][] solve(int[][] A) { // TODO: Implement solution return new int[0][0]; } }