DSA interview question

Floyd–Warshall Algorithm (All-Pairs Shortest Paths)

Hard · Algorithms · Topics: graph, floyd warshall, dp

The problem

A logistics planner needs the shortest travel cost between every pair of depots, given as an adjacency matrix where −1 means "no direct route". Running Dijkstra from every depot works, but for dense graphs the triple loop of Floyd–Warshall is simpler. For each possible intermediate depot k, check whether going through k improves the cost from i to j. After every k has been considered, the matrix holds all shortest paths.

Example: [[0,1,43], [1,0,6], [-1,-1,0]] → [[0,1,7], [1,0,6], [-1,-1,0]].

Function signature

void shortestDistance(vector<vector<int>>& matrix);  // in place; -1 = no path

Test cases

Input matrix	Output matrix	Explanation
`[[0,1,43],[1,0,6],[-1,-1,0]]`	`[[0,1,7],[1,0,6],[-1,-1,0]]`	0→2 via 1 costs 7
`[[0,4,-1],[-1,0,2],[1,-1,0]]`	`[[0,4,6],[3,0,2],[1,5,0]]`	Every pair becomes reachable
`[[0,25],[-1,0]]`	`[[0,25],[-1,0]]`	1 can't reach 0
`[[0,-1],[-1,0]]`	`[[0,-1],[-1,0]]`	No edges
`[[0]]`	`[[0]]`

(Confirm: the matrix is directed; −1 marks "no edge" (not a negative weight); weights are non-negative; the diagonal is 0.)

How interviewers phrase it

"Given a weighted adjacency matrix, find the shortest distances between every pair of vertices, in place; −1 means no edge" (GeeksforGeeks "Floyd Warshall").

Clarifying questions to ask

Directed or undirected? (Directed in general.)
What does −1 mean? (No edge. It isn't a weight.)
Can weights be negative? (Floyd–Warshall handles negative edges, and a negative diagonal then reveals a negative cycle. Here weights are non-negative.)

Follow-ups to expect

"What does the k loop mean?"
"How do you handle −1 correctly?"
"How would you detect negative cycles?"
"When should you prefer Dijkstra V times?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview