8

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.)

Improve this question
2
  • 1
    Dijkstra's algo is A* with h=0, wrt to the 'pathfinding' do you mean that you have no way to estimate a better minimum cost?
    – jk.
    Apr 3, 2013 at 7:20
  • 1
    Setting the shortest-path-found attribute of every vertex doesn't mean you have to write 'infinity' one billion times. You just need a function that returns 'infinity' when no value is set.
    – kevin cline
    Apr 3, 2013 at 22:16

3 Answers 3

Reset to default
6

Basic Algorithm

Maintain two sets of the nodes you can reach from the start and end node. In alternating fashion, go three steps from both sides. Each time replacing your set with nodes you can reach through one more step. After each step you check the two sets for common nodes.

Optimizations

Make sure you can iterate the sets as sorted so that you can search for common nodes in a single sweep: an O(n+m) operation. Lists will be up to a million nodes each.

To extend a set with one step, you have query all connections of the nodes in the original set and merge them into a new sorted set. Merging 2 sorted lists can again be done in a single sweep. So you also want to make sure that you can query the connections of a node as sorted. (This could be preprocessed).

In the last two steps each new set is the result of merging up to 10000 of these query results. It is best to do this merge adaptive (merging equally sized chunks). In that way, the sorted set data structure can be a simple linked list.

That way the whole algorithm becomes O(6*n + 6*n*log n) where n is max. 1,000,000.

Improve this answer
5
  • How do you check for membership in a linked list in less than O(n)? That seems like a big problem.
    – Nick ODell
    Apr 3, 2013 at 17:07
  • The trick is to run over both lists simultaneously. That way you can check for any doubles in a single sweep.
    – Kris Van Bael
    Apr 3, 2013 at 21:02
  • Won't insertion get expensive using a sorted list? A tree or hash would work better.
    – kevin cline
    Apr 3, 2013 at 22:21
  • A tree might indeed be better. But either way, the insertion is optimized by having all connections of a node pre-sorted.
    – Kris Van Bael
    Apr 4, 2013 at 21:59
  • Or rather... Single linked list is perfectly fine. See edits of the answer.
    – Kris Van Bael
    Apr 4, 2013 at 23:07
2

Just use breath first search (no need for Dijkstra's alg. because all edges have uniform length) (and as Kris Van Bael said, run it from both sides)

Improve this answer
0

"All edges have a length of 1" This is a best-case scenario making Dijkstra's Algorithm a perfect greedy algorithm choice. Even using the Floyd-Warshall algorithm involving fast matrix multiplication would work well.

Improve this answer
2
  • I'm confused. From the link you gave, it looks like the Floyd-Warshall algorithm is aimed towards solving the all-pairs shortest path problem. Is it also best way to find distance between a single pair?
    – Nick ODell
    Apr 3, 2013 at 17:24
  • @NickODell Floyd-Warshall is a greedy algorithm for finding shortest paths in a graph. It is but one, including Dijkstra which is quite popular, for finding shortest paths from the start node to all other nodes. Remember, you are finding the shortest path from a designated node to all other nodes and not just two points.
    – Mushy
    Apr 3, 2013 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.