Shortest Path in Adjacency Matrix | Dataford Interview Questions

Given a connected, undirected graph represented by an n x n Boolean adjacency matrix where matrix[i][j] = true indicates an edge, write a function that takes two vertex indices and returns the shortest distance between them measured by the minimum number of edges.

Asked in the Phone Screen stage. Use breadth-first search because every edge has equal cost. The function receives matrix, start, and end, and returns an integer distance.

Constraints

1 <= n <= 10^3
matrix has exactly n rows and n Boolean entries per row
The graph is connected and undirected
0 <= start, end < n

Function Signature

def shortest_distance(matrix, start, end):

Your question is Shortest Path in Adjacency Matrix. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Asked in the Phone Screen stage. Use breadth-first search because every edge has equal cost. The function receives matrix, start, and end, and returns an integer distance.

Constraints

1 <= n <= 10^3
matrix has exactly n rows and n Boolean entries per row
The graph is connected and undirected
0 <= start, end < n

Function Signature

def shortest_distance(matrix, start, end):

Your question is Shortest Path in Adjacency Matrix. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.