Shortest Distance in an Unweighted Adjacency-Matrix Graph

You are given the Boolean adjacency matrix of a connected, undirected, unweighted graph. Return the minimum number of edges on a path between two specified vertices.

Implement shortestDistance(matrix, vertex1, vertex2).

Input and Output

• matrix is an n x n Boolean matrix.
• matrix[i][j] is true exactly when an edge joins vertices i and j.
• vertex1 and vertex2 are zero-based vertex indexes.
• Return the fewest edges needed to travel from vertex1 to vertex2.

Constraints

• 1 <= n <= 2,000
• matrix[i][i] is always false.
• matrix[i][j] == matrix[j][i] for all valid i and j.
• The graph has no loops or parallel edges and is connected.
• 0 <= vertex1, vertex2 < n
• If the two vertices are equal, return 0.

Example 1

Input: matrix = [[false, false, true], [false, false, true], [true, true, false]], vertex1 = 0, vertex2 = 1
Output: 2

One shortest path is 0 -> 2 -> 1.

Example 2

Input: matrix = [[false, true, false, false], [true, false, true, true], [false, true, false, false], [false, true, false, false]], vertex1 = 2, vertex2 = 3
Output: 2

One shortest path is 2 -> 1 -> 3.

Shortest Distance in an Unweighted Adjacency-Matrix Graph

Hints

1. In an unweighted graph, explore vertices in layers of increasing edge distance.
2. An adjacency matrix requires scanning a whole row to find a vertex's neighbors.

Approach

Run breadth-first search from vertex1. The queue processes vertices by nondecreasing distance, so the first discovery of any vertex uses the fewest possible edges. For each dequeued vertex, scan its entire adjacency-matrix row and enqueue every unvisited neighbor with distance one greater. Return as soon as vertex2 is discovered; equal endpoints are handled before the search.

• Time complexity: O(n^2), because each visited vertex scans one row of the n by n adjacency matrix.
• Space complexity: O(n) for the distance array and BFS queue, excluding the input matrix.