Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
Breadth-first search? –  Long Oct 5 '12 at 15:59
    
@Long It didn't take you Long to come up with that. –  Graphth Oct 5 '12 at 16:40

3 Answers 3

up vote 2 down vote accepted

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$.

share|improve this answer
    
!! This is exactly what I need! –  Arkamis Oct 5 '12 at 16:09
    
@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. –  Graphth Oct 5 '12 at 16:11
    
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. –  Arkamis Oct 5 '12 at 16:15
    
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 :) –  Arkamis Oct 5 '12 at 16:18
    
A bit of trivia: This is the solution to the famous math problem in the film "Good Will Hunting". –  axblount Oct 5 '12 at 16:45

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.

share|improve this answer
    
Excellent, exactly what I need to get started. Thanks! –  Arkamis Oct 5 '12 at 16:08

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.