Shortest Path in Adjacency Matrix

MediumPython

Problem

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):

CodePython 3

You need to log in / sign up to run or submit.Ln 2

Run your code to see test output here.