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.

  • 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
    I'm using this $p$roperty in $a$ report. Is there $a$ny paper/book c$h$apter 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$.