Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

share|improve this question
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 '13 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 '13 at 22:16
add comment

3 Answers

up vote 5 down vote accepted

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.

share|improve this answer
    
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 '13 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 '13 at 21:02
    
Won't insertion get expensive using a sorted list? A tree or hash would work better. –  kevin cline Apr 3 '13 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 '13 at 21:59
    
Or rather... Single linked list is perfectly fine. See edits of the answer. –  Kris Van Bael Apr 4 '13 at 23:07
add comment

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)

share|improve this answer
add comment

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

share|improve this answer
    
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 '13 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 '13 at 17:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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