`nearest`

Nodes within a given distance of a node.

Category: Mathematics > Graph and Network Algorithms

Syntax

nodes = nearest(G, s, d)

Returns the nodes whose shortest-path distance from s is at most d.

[nodes, dist] = nearest(G, s, d)

Also returns those distances.

Description

It answers neighborhood questions such as which towns are within 50 km by road. With unweighted edges, d counts steps, so nearest(G, s, 1) is the same set as neighbors(G, s) but sorted by distance. In a digraph, distances follow edge directions.

Input arguments

G: A graph or digraph. Weights, if present, are edge lengths.
s: Center node.
d: Maximum distance.

Output arguments

nodes: Column vector of node indices, nearest first. The node s itself is not included.
dist: Column vector with the distance to each returned node.

Example

Within distance 3

G = graph([1 1 2 2 3 4], [2 3 3 4 4 5], [2 1 3 5 1 4]);
[n, d] = nearest(G, 1, 3);
[n d]

Output

nearest