Floyd-Warshall Algorithm
Shortest Path Algorithms DSA practice problem on Onlearn.
Difficulty: hard.
Topics: All-Pairs Shortest Paths in a Directed Weighted Graph (Floyd-Warshall Algorithm), Graph, Adjacency Matrix, Weighted Graph, Directed Graph, Shortest Path, Floyd Warshall Algorithm, Dynamic Programming, Time Complexity, Space Complexity, In-place Algorithm, Brute Force, Matrices, Cycle Detection, Dijkstra's Algorithm, Bellman-Ford Algorithm, in-place algorithms, graph representation, complexity analysis, edge cases, brute force, floyd-warshall algorithm, shortest path algorithms, cycle detection, Shortest Path (Floyd-Warshall), In-Place Algorithms, Graph Traversal Utilities.
""" Problem Statement Given an n x n integer matrix representing an edge weighted directed graph, find the shortest distances between every pair of vertices. matrix[i][j] denotes the weight of the edge from vertex i to vertex j. If matrix[i][j] = 1, it means there is no edge from i to j. The task is to modify the input matrix in place to store the shortest distances. Input Format The input consists of an n x n integer matrix. Output Format The output should be the modified matrix where matrix[i][j] stores the shortest distance from vertex i to vertex j. If there is no path between i and j, matrix[i][j] should remain 1 (or the equivalent representation used internally for infinity). Constraints 1 <= n <= 100 (Assumed based on typical competitive programming constraints for O(V^3) algorithms and given examples) Edge weights will be integers. 1 indicates no edge. Sample Test Cases Example 1: Input: Output: Explanation: The final matrix stores the shortest distances. For example, matrix[i][j] is storing the shortest distance from node i to j. Example 2: Input: Output: Explanation: In this example, the shortest distance is already given (if it exists)."""