Floyd Warshall

Medium
1679.

Floyd Warshall

Floyd Warshall is a medium coding problem on dynamic programming, graph and shortest path, asked in Amazon, Flipkart and Samsung interviews.

A weighted directed graph with n vertices, numbered 0 to n - 1, is given as an n x n adjacency matrix matrix:

  • matrix[i][j] is the weight of the edge from i to j, or -1 if there is no such edge,
  • matrix[i][i] is always 0.

Return the matrix of shortest distances: entry [i][j] is the length of the shortest path from i to j, or -1 if j cannot be reached from i. A vertex is at distance 0 from itself.

Example 1

Input
matrix = [[0,25],[-1,0]]
Output
[[0,25],[-1,0]]
Explanation
Vertex 1 has no outgoing edge, so it reaches nothing but itself.

Example 2

Input
matrix = [[0,1,43],[1,0,6],[-1,-1,0]]
Output
[[0,1,7],[1,0,6],[-1,-1,0]]
Explanation
Going 0 → 1 → 2 costs 1 + 6 = 7, cheaper than the direct edge of 43.

Example 3

Input
matrix = [[0]]
Output
[[0]]

Constraints

  • 1 <= n <= 100
  • matrix.length == matrix[i].length == n
  • matrix[i][i] == 0
  • matrix[i][j] == -1 or 1 <= matrix[i][j] <= 1000 for i != j
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} matrix
 * @return {number[][]}
 */
var shortestDistance = function(matrix) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Floyd Warshall — Solution in Python, Java & C++

Floyd Warshall solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Floyd Warshall is a medium coding problem on dynamic programming, graph and shortest path, asked in Amazon, Flipkart and Samsung interviews.

Problem statement

A weighted directed graph with n vertices, numbered 0 to n - 1, is given as an n x n adjacency matrix matrix:

  • matrix[i][j] is the weight of the edge from i to j, or -1 if there is no such edge,
  • matrix[i][i] is always 0.

Return the matrix of shortest distances: entry [i][j] is the length of the shortest path from i to j, or -1 if j cannot be reached from i. A vertex is at distance 0 from itself.

Example 1

Input: matrix = [[0,25],[-1,0]]
Output: [[0,25],[-1,0]]
Explanation: Vertex 1 has no outgoing edge, so it reaches nothing but itself.

Example 2

Input: matrix = [[0,1,43],[1,0,6],[-1,-1,0]]
Output: [[0,1,7],[1,0,6],[-1,-1,0]]
Explanation: Going 0 → 1 → 2 costs 1 + 6 = 7, cheaper than the direct edge of 43.

Example 3

Input: matrix = [[0]]
Output: [[0]]

Constraints

  • 1 <= n <= 100
  • matrix.length == matrix[i].length == n
  • matrix[i][i] == 0
  • matrix[i][j] == -1 or 1 <= matrix[i][j] <= 1000 for i != j

Hints for Floyd Warshall

  1. Hint 1

    A shortest path from i to j either avoids vertex k or goes i → … → k → … → j, joining two shorter shortest paths.

  2. Hint 2

    Let d[i][j] be the best distance using only intermediate vertices from {0, …, k}. Adding vertex k can only improve d[i][j] to d[i][k] + d[k][j].

  3. Hint 3

    Treat -1 as infinity while relaxing, loop k outermost, and turn infinity back into -1 at the end.

How to solve Floyd Warshall

Floyd–Warshall is a dynamic programme over the set of vertices a path may pass through. After processing vertices 0..k as possible intermediates, d[i][j] holds the shortest i → j path whose interior uses only those vertices.

Approach

  1. Copy the matrix, replacing every -1 with a large sentinel INF (any value above the longest possible path, e.g. 10^8).
  2. For k from 0 to n - 1, for every pair (i, j): if d[i][k] + d[k][j] < d[i][j], update d[i][j].
  3. Replace every entry still at INF with -1 and return the matrix.

Why it works

Consider the shortest i → j path whose interior vertices are all below k + 1. If it does not use k, it was already found in round k - 1. If it does, it visits k once (weights are positive, so a cycle never helps), splitting into an i → k and a k → j path whose interiors are below k — both already optimal in d — so the update in round k finds it. By induction the final table is exact.

Complexity

  • Time — O(n^3)
  • Space — O(n^2)

Pitfalls

  • The loop over the intermediate vertex k must be the outermost one; putting it inside the i/j loops gives wrong answers.
  • Do not add to -1 directly — convert it to a sentinel first, or a missing edge looks like a negative shortcut.
  • Keep the sentinel small enough that INF + INF cannot overflow a 32-bit integer.

Reference solution

Python

from typing import List

def shortestDistance(matrix: List[List[int]]) -> List[List[int]]:
    n = len(matrix)
    INF = 10 ** 8
    d = [[INF if v == -1 else v for v in row] for row in matrix]
    for k in range(n):
        dk = d[k]
        for i in range(n):
            dik = d[i][k]
            if dik == INF:
                continue
            di = d[i]
            for j in range(n):
                if dik + dk[j] < di[j]:
                    di[j] = dik + dk[j]
    return [[-1 if v >= INF else v for v in row] for row in d]

Java

public static int[][] shortestDistance(int[][] matrix) {
    int n = matrix.length, INF = 100000000;
    int[][] d = new int[n][n];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) d[i][j] = matrix[i][j] == -1 ? INF : matrix[i][j];
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++) {
            if (d[i][k] == INF) continue;
            for (int j = 0; j < n; j++)
                if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
        }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) if (d[i][j] >= INF) d[i][j] = -1;
    return d;
}

C++

vector<vector<int>> shortestDistance(vector<vector<int>>& matrix) {
    int n = matrix.size(), INF = 100000000;
    vector<vector<int>> d(n, vector<int>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) d[i][j] = matrix[i][j] == -1 ? INF : matrix[i][j];
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++) {
            if (d[i][k] == INF) continue;
            for (int j = 0; j < n; j++)
                if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
        }
    for (auto& row : d)
        for (auto& v : row) if (v >= INF) v = -1;
    return d;
}

JavaScript

var shortestDistance = function(matrix) {
    var n = matrix.length, INF = 100000000;
    var d = [];
    for (var i = 0; i < n; i++) {
        var row = [];
        for (var j = 0; j < n; j++) row.push(matrix[i][j] === -1 ? INF : matrix[i][j]);
        d.push(row);
    }
    for (var k = 0; k < n; k++) {
        for (var a = 0; a < n; a++) {
            if (d[a][k] === INF) continue;
            for (var b = 0; b < n; b++) {
                if (d[a][k] + d[k][b] < d[a][b]) d[a][b] = d[a][k] + d[k][b];
            }
        }
    }
    for (var x = 0; x < n; x++) for (var y = 0; y < n; y++) if (d[x][y] >= INF) d[x][y] = -1;
    return d;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming · Graph Data Structure