Shortest Distance in an Unweighted Adjacency-Matrix Graph

Shortest Distance in an Adjacency Matrix

You are given an undirected, unweighted graph with n vertices labeled from 0 to n - 1. The graph is represented by an n x n binary adjacency matrix adj_matrix, where adj_matrix[i][j] == 1 indicates an edge between vertex i and vertex j, and 0 indicates no direct edge.

Given two vertex indices src and dst, compute the minimum number of edges in a path connecting src to dst. If src == dst, the distance is 0. If no path exists, return -1.

Function Signature

def shortest_distance(adj_matrix: list[list[int]], src: int, dst: int) -> int:
    pass

Input

• adj_matrix: A 2D list of integers of size n x n, where adj_matrix[i][j] in (0, 1). The matrix is symmetric (adj_matrix[i][j] == adj_matrix[j][i]) and contains no self-loops (adj_matrix[i][i] == 0).
• src: An integer representing the starting vertex (0 <= src < n).
• dst: An integer representing the target vertex (0 <= dst < n).

Output

• An integer representing the shortest path length (number of edges) between src and dst, or -1 if unreachable.

Constraints

• 1 <= n <= 1000
• 0 <= src, dst < n
• adj_matrix[i][i] == 0 for all 0 <= i < n
• adj_matrix[i][j] == adj_matrix[j][i] for all 0 <= i, j < n

Examples

Example 1:

adj_matrix = [
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 1],
    [0, 1, 1, 0]
]
src = 0
dst = 3
# Output: 2
# Explanation: The shortest paths are 0 -> 1 -> 3 or 0 -> 2 -> 3, both taking 2 edges.

Example 2:

adj_matrix = [
    [0, 1, 0],
    [1, 0, 0],
    [0, 0, 0]
]
src = 0
dst = 2
# Output: -1
# Explanation: Vertex 2 is disconnected from vertex 0.

Example 3:

adj_matrix = [
    [0, 1],
    [1, 0]
]
src = 1
dst = 1
# Output: 0
# Explanation: Source and destination are identical.

Edge Cases to Consider

• src == dst: Should immediately return 0.
• Disconnected components: Must return -1 if no path exists.
• Dense graphs: Scanning each row in the adjacency matrix takes O(n) time per vertex visited.