Ref question: K-nearest neighbours in a graph Given an undirected  graph $G$  with $n$ vertices,  $m$ edges, and positive weights on the edges, I am interested in the problem of computing for each vertex the $k$ distinct vertices in $G$ that are closest to it on the shortest-path distances in $G$. There is a solution that follows by modifying Dijkstra, where the running time is $k$ times the running time of the standard Dijkstra. Anybody knows a ref to this result? Should I bother to write this down?

thanks....

Update: I wrote down my algorithm in case anybody is interested... 
http://sarielhp.org/p/14/k_nn/
In Victor Teixeira de Almeida, Ralf Hartmut Güting: Using Dijkstra's algorithm to incrementally find the k-Nearest Neighbors in spatial network databases. SAC 2006: 58-62, Teixeira and Güting describe a new storage schema with a set of indexed structures to support an efficient
execution of a slightly modified version of the Dijkstra's algorithm.

In the introduction they simply use the reference to the original Dijkstra's paper:

... An obvious modification on Dijkstra's algorithm 
[reference to the original Dijkstra's 1967 paper] that computes shortest path between objects could be done in order to compute the k-NN using the network space.
But, in this case, sepcial storage schemas are necessary in order to
efficiently support this algorithm. In this paper, ...

So I think you can use the same approach: if your work is NOT focused on a new variant of a k-NN algorithm you can simply mention it and cite Dijkstra's paper; otherwise you should also include other references on the subject; I think there are many of them because the k-NN problem is important, for example, in navigation systems; googling around I found: Fast Nearest Neighbor Search on Road Networks, Alternative Solutions for Continuous K-NN Queries in Spatial Network Databases, ...