On Fri, Oct 2, 2009 at 9:42 AM, Ralf Goertz
Hi,
I have some very large undirected graphs (half a million vertices). Edges have weight 0 or 1. For each vertex I need to find all vertices
* that are in sum 2 edges away * whose distance is 0
Both tasks can be done with breadth-first searches but I don't know in advance how many edges in depth I have to traverse. That's why I thought of Dijkstra's algorithm. But in my case this is overkill as I am not interested in the exact distance of a vertex from a given vertex but only in if it is not farther than 0 or 2 away. Is it possible to use a visitor to alter the colormap to mark vertices as final that are too far even thought they are not final yet?
I don't have a suggestion, but I did want to lend weight to your question since I have exactly the same requirements. I currently use Dijkstra and accept the overkill, but as my graphs get bigger it's becoming less acceptable. --Michael Fawcett