Thanks for the Goldberg pointer. I have a rudimentary bidirectional, parallel BFS working which I'll be blogging about once it's ready. It runs very fast even on huge graphs.