How should I practice Shortest Distances From an Adjacency Matrix?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Boston Consulting Group phone screen problems in FastPrep.

Is Shortest Distances From an Adjacency Matrix associated with Boston Consulting Group?

FastPrep tags this as a Boston Consulting Group phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Graph

Shortest Distances From an Adjacency Matrix

Learn this problem

● Medium

Boston Consulting GroupFULLTIMEPHONE SCREEN

Problem statement

You are given a connected, undirected graph as an integer adjacency matrix matrix, plus zero-based vertices source and target.

For distinct vertices, matrix[u][v] = 0 means there is no edge. A positive entry is the weight of the edge. The matrix is symmetric, every diagonal entry is zero, and the graph has no loops or multiple edges.

Return a two-element array of 64-bit integers:

The fewest edges in any path from source to target, ignoring edge weights.
The smallest sum of edge weights in any path from source to target.

These two minima are independent: the fewest-edge path need not have the least total weight. If the two vertices are equal, return [0,0]. Because the graph is connected, both answers always exist.

Function

shortestDistances(matrix: int[][], source: int, target: int) → long[]

Examples

Example 1

matrix = [[0,2,10],[2,0,3],[10,3,0]]source = 0target = 2return = [1,5]

The direct edge 0 → 2 uses one edge but costs 10. The path 0 → 1 → 2 uses two edges and costs only 2+3=5.

Example 2

matrix = [[0,4,0,0],[4,0,6,0],[0,6,0,2],[0,0,2,0]]source = 3target = 0return = [3,12]

The only simple route is 3 → 2 → 1 → 0, with three edges and total weight 2+6+4=12.

Constraints

1 <= matrix.length <= 50, and matrix is square.
0 <= matrix[u][v] <= 1000000.
matrix[u][v] = matrix[v][u], and matrix[u][u] = 0.
Positive entries define one connected graph.
0 <= source, target < matrix.length.