0
$\begingroup$

This question may be better served at cs.SE, but I am not very familiar with CS lingo, so I'm hoping the maths community would be able to answer it as well...

I have an undirected graph, and I am interested in finding all vertices in the graph exactly $k$ steps away from a given vertex. In other words, I want to compute the set of all vertices such that the closest path is $k$ steps away.

Is there such an algorithm, or is there an obvious modification to a different algorithm? I'm sure that something like Djikstra's algorithm can solve it brute force by computing the shortest path to each vertex, but I'm hoping that there is something more cleverer that doesn't resort to brute-forciness.

  • 1
    Breadth-first search?2012-10-05
  • 0
    @Long It didn't take you Long to come up with that.2012-10-05

3 Answers 3

4

Another algorithm... let $A$ be the adjacency matrix of the graph. Consider successive powers of $A$, $A, A^2, A^3, \ldots A^k$. A vertex $u$ is distance $k$ from a vertex $v$ if and only if the $u, v$ entry of $A, A^2, \ldots, A^{k-1}$ are all $0$ and the $u, v$ entry of $A^k$ is not zero. In general, the $uv$ entry of $A^j$ is the number of walks from $u$ to $v$ of length $j$.

  • 0
    !! This is exactly what I need!2012-10-05
  • 0
    @EdGorcenski Why do you need this, by the way? For small graphs, this is probably instantaneous. For larger graphs, you'd probably go with Henning's answer. This one has the advantage that it's very simple and easy to program. But, if you wanted such a thing, maybe it's already in Sage... hmm. Yes, it looks like in fact it is called "breadth_first_search". My point here is just that a lot of graph theory stuff is already programmed if you wanted to use that instead of reinventing the wheel.2012-10-05
  • 0
    I have a map of a virtual city, and a user is instructed to navigate the city using certain contextual clues, placed at intersections. The user needs to make a certain number of decisions (tests), and so I need to be able to find a subset of intersections at which I can position objectives that ensure that the user encounters a pre-specified number of tests.2012-10-05
  • 0
    I'm sure there's stuff out there; for now, I'm doing the analysis in MATLAB, and I can probably find code that does exactly what I need. My reason for posting the question is that I wasn't even sure what I needed to look for at first :)2012-10-05
  • 0
    A bit of trivia: This is the solution to the famous math problem in the film "Good Will Hunting".2012-10-05
  • 0
    @axblount I knew that that problem had something to do with computing adjacency matrices, but I didn't know that it was specifically this. Interesting! Graph theory is one of the many branches of mathematics in which my background is badly deficient.2012-10-05
  • 0
    This works, but I find it funny that that @Ed would prefer it over a "brute force" approach that is likely to be much faster.2012-10-05
  • 0
    @HenningMakholm The adjacency matrix method has some possible advantages in terms of how I plan to utilize the data. Computational speed is no issue; the map is static, and I need only compute the data one time (and the map is not sufficiently large that I am terribly worried). Nevertheless, I will experiment with both approaches.2012-10-05
  • 0
    I'm using this property in a report. Is there any paper/book chapter I could cite? I couldn't find any.2015-04-23
3

A standard breadth-first traversal of the graph will visit the vertices in order of increasing distance from the starting node.

Furthermore, each node will get added to the work list while you're looking at the next-to-last node in a shortest path to the target node -- so you can store the distance to each node in the order they get added to the worklist.

Once you see a node with distances $k+1$, you can stop everything.

This search is linear in the number of edges within $k$ of the starting node.

  • 0
    Excellent, exactly what I need to get started. Thanks!2012-10-05
1

Call the vertex $v$.

$d(v, v) = 0$

The vertices, $u$, that satisfy $d(u, v) = 1$, are exactly the neighbors of $v$.

The vertices, $w$, that satisfy $d(w, v) = 2$, are exactly the neighbors of neighbors of $v$ that have not yet been used.

And so on. Keep going until you get to distance $k$.