I have a graph with about a billion vertices, each of which is connected to about 100 other vertices at random.
I want to find the length of the shortest path between two points. I don't care about the actual path used.
Notes:
- Sometimes edges will be severed or added. This happens about 500 times less often than lookups. It's also ok to batch up edge-changes if it lets you get better performance.
- I can pre-process the graph.
- If it takes more than 6 steps, you can just come back with infinity.
- It's acceptable to be wrong 0.01% of the time, but only in returning a length that's too long.
- All edges have a length of 1.
- All edges are bidirectional.
I'm looking for an algorithm. Psuedocode, english descriptions, and actual code are all great.
I could use A*, but that seems optimized for pathfinding.
I thought about using Dijkstra's algorithm, but it has a step which requires setting the shortest-path-found attribute of every vertice to infinity
(If you're wondering about the use-case, it's for the Underhanded C Contest.)