Coding

Floyd warshall algorithm

Asked at

Microsoft

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given a graph of V vertices numbered from 0 to V-1. Find the shortest distances between every pair of vertices in a given edge-weighted directed graph. The graph is represented as an adjacency matrix of size n x n. Matrix[i][j] denotes the weight of the edge from i to j. If matrix[i][j]=-1, it means there is no edge from i to j.

Input: matrix = [[0, 2, -1, -1],[1, 0, 3, -1],[-1, -1, 0, 1],[3, 5, 4, 0]] Output: [[0, 2, 5, 6], [1, 0, 3, 4], [4, 6, 0, 1], [3, 5, 4, 0]] Explanation: matrix[0][0] is storing the distance from vertex 0 to vertex 0, the distance from vertex 0 to vertex 1 is 2 and so on.

Input: matrix = [[0,25],[-1,0]] Output: [[0, 25],[-1, 0]] Explanation: The matrix already contains the shortest distance.

Input: matrix = [[0,1,43],[1,0,6],[-1,-1,0]]

1 <= n <= 100
-1 <= matrix[ i ][ j ] <= 1000

cpp

class Solution {
public:
	void shortestDistance(vector<vector<int>>&matrix) {
	
	}
};

java

class Solution {
    public void shortestDistance(int[][] matrix) {
  
    }
}

python

class Solution:
    def shortestDistance(self, matrix):

javascript

class Solution {
    shortestDistance(matrix) {
      
    }
}

csharp

class Solution
{
    public void shortestDistance(int[][] matrix)
    {

    }
}

func ShortestDistance(matrix [][]int) {
	
}

Stuck? Show a way to structure it+

01Initialize the adjacency matrix carefully
02Loop k outermost, then i and j
03Skip additions involving infinity
04Optionally inspect dist[i][i] for negative cycles

Reference answer

Start by restating the input contract for Floyd warshall algorithm and testing the smallest boundary case before choosing the algorithm. Initialize dist[i][j] with edge weights, zero on the diagonal, and infinity otherwise. For every possible intermediate k, relax each pair i,j through k. After k is processed, dist represents shortest paths using only intermediates up to k. Explain the invariant while coding, then show how each update preserves it. The three nested vertex loops make Floyd-Warshall O(V^3) time and the distance matrix is O(V^2) space. Walk through one nontrivial example aloud so the interviewer can see why the method reaches the intended result. Finally, call out input assumptions and failure cases rather than silently relying on them. A clean implementation should keep state local, use descriptive names, and avoid work that the invariant makes unnecessary.

Then expect these follow-ups

How can you reconstruct paths?
Tests: implementation extension
When is repeated Dijkstra preferable?
Tests: follow-up reasoning

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question