Message Route — Editorial

Opening the reading…

Intuitionwhy BFS gives the minimum route

A route is shortest when it uses the fewest connections, or equivalently the fewest computers after its starting computer is fixed. Every connection costs exactly one step, so the useful question is not which neighbor looks promising, but which computers are exactly 1, then 2, then 3 connections away from computer 1.

Breadth-first search visits the network in those distance layers. The first time it discovers a computer, it has reached that computer using the fewest possible connections, because every shorter layer has already been processed. Store the computer from which each new computer was discovered. Once computer n is found, following those predecessor links backward gives a shortest route, which you reverse before returning.

Approach

Build an adjacency list and add both endpoints for every connection, because the network is undirected and omitting one direction can hide valid routes.

Create a predecessor array filled with -1, set predecessor[1] to 0, and enqueue computer 1, because this both marks the start as discovered and gives reconstruction a clear stopping marker.

Repeatedly remove the front computer from the queue, because FIFO order processes all computers at one distance before any computer farther away.

For every neighbor that still has predecessor -1, record the current computer as its predecessor and enqueue it, because the first discovery is its shortest known route and preventing later discoveries avoids cycles and duplicate work.

Stop when the queue is empty or computer n is removed, because an empty queue proves that n is unreachable, while removing n means all shorter distance layers have already been explored.

If predecessor[n] is still -1, return an empty array, because no search edge ever reached the destination.

Starting at n, append each computer and replace it with its predecessor until reaching 0, then reverse the collected array, because predecessor links point from destination to start while the required route must be returned in the opposite order.

Complexitylinear in the network size

MEASURE	BOUND	WHY
Time	O(n + m)	Building the adjacency list examines each connection once. BFS removes each discovered computer once and scans each adjacency entry once; an undirected connection appears in two lists, which is still a constant two scans, so no edge is counted more than twice.
Space	O(n + m) extra	The adjacency lists hold two entries per connection, while predecessor and the queue hold at most one entry per computer. The returned route is required output and is excluded from extra space. In the worst shape, a dense allowed graph makes m dominate the storage, while a sparse graph uses O(n) extra space.

Here n is the number of computers and m is the number of undirected connections.

Annotated solutionC++ · adjacency list, BFS, and predecessor reconstruction

CPPBFS records one predecessor per computer, then reverses the destination-to-start chain.

#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> findShortestRoute(int n, vector<vector<int>> edges) {
        vector<vector<int>> graph(n + 1);
        for (const vector<int>& edge : edges) {
            int a = edge[0];
            int b = edge[1];
            graph[a].push_back(b);
            graph[b].push_back(a);
        }

        vector<int> parent(n + 1, -1);
        queue<int> q;
        parent[1] = 0;
        q.push(1);

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            if (u == n) {
                break;
            }

            for (int v : graph[u]) {
                if (parent[v] == -1) {
                    parent[v] = u;
                    q.push(v);
                }
            }
        }

        if (parent[n] == -1) {
            return {};
        }

        vector<int> route;
        for (int v = n; v != 0; v = parent[v]) {
            route.push_back(v);
        }
        reverse(route.begin(), route.end());
        return route;
    }
};

The predecessor array serves two jobs. A value of -1 means the computer has not been discovered, so it is the visited check; after discovery, the stored value tells reconstruction exactly where to step next. Setting parent[1] to 0 prevents the start from being rediscovered through a cycle and makes the reconstruction loop stop cleanly.

The early break is safe because the queue is FIFO. When n reaches the front, every computer that could be reached in fewer steps has already been removed and expanded, so the predecessor recorded for n belongs to a shortest route. If you omit the break, the answer remains correct; the break simply avoids scanning irrelevant later layers.