Problem 61063. The Bridges of Nedsburg

The fabled city of Nedsburg consists of several islands connected by bridges. Due to tectonic forces, shoddy civil engineering, and the whims of the city's capricious dictator, Lord Ned, the number of islands and the arrangement of bridges are constantly changing.
Therefore, instead of a map, visitors to Nedsburg are given a connectivity matrix (C): a square matrix of 0s and 1s, where C(j,k) = 1 if there is a bridge from island j to island k, and C(j,k) = 0 if not. Lord Ned’s diabolical nature means that the bridges can be one-way only. This means C is not necessarily symmetric. That is, it is possible to have C(j,k) = 1 (you can travel directly from island j to island k) and C(k,j) = 0 (you can’t travel directly from island k to island j).
Because Lord Ned likes to torture visitors with math problems, the Nedsburg transit system has an n-bridge pass which allows you to cross up to n bridges in one journey. Not surprisingly, the pricing scheme gets eye-wateringly expensive as n increases and once you purchase your pass, you are locked in to that price (at least until the connectivity matrix changes). Visitors are therefore advised to pick the smallest possible value of n that allows them to get from any island to any other island in one journey.
To prepare for your upcoming trip to Nedsburg to watch the Nedball World Cup, you need to write a function that, given C, returns the minimum n needed so that there is a path from every island to every other island in n steps or fewer. That is, find the smallest n such that every pair of islands is at most n bridges away from each other.
A handy bit of math that might help is that the value of represents the number of paths of exactly m steps from island j to island k. (Here, is the matrix power; that is, , using matrix multiplication.) Therefore, if , then there is no way to get from j to k in exactly m steps. If , there is at least one path (of m steps) from j to k. Therefore, one way to solve the problem is to find the smallest n such that, for every j,k pair, there is some m ≤ n such that .
Example
Consider this arrangement of three islands with four bridges (1→2, 1→3, 2→3, 3→1)
There are no bridges to get from 2 to 1 or from 3 to 2 in one step. However,
C = [0 1 1;0 0 1;1 0 0];
C^2
ans =
1 0 1
1 0 0
0 1 1
This means it is possible to get from 2 to 1 and from 3 to 2 in two steps. While there is no 2-step path from 3 to 1, this can be achieved in one step (C(3,1) = 1). So in this case, n = 2: you can get from every island to every other island with a journey that crosses no more than two bridges.
The matrices C and C^2 are shown in two different colors. A grid representing all the possible pairs of nodes has entries in each location showing the minimum number of steps, and the associated path, needed to travel between each pair. (The diagonal entries are blank, as these would represent traveling to the same node/island.) The four non-zero elements of C correspond to four pairs of islands that are connected with a single-step journey. The remaining two pairs (2 to 1 and 3 to 2) are connected with two-step journeys.
Assumptions
While it is dangerous to expect too much rational behavior from Lord Ned, he won't strand his citizens, so you can assume that a finite n exists for the given connectivity matrix C. This also means the problem is trivial for one or two islands, so your solution only needs to work when C is at least 3-by-3.
Solve

Solution Stats

66.13% Correct | 33.87% Incorrect
Last Solution submitted on Nov 14, 2025

Problem Comments

Solution Comments

Show comments

Problem Recent Solvers38

Suggested Problems

More from this Author33

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!