Qual algoritmo devo usar para encontrar o caminho mais curto neste gráfico?

Eu tenho um gráfico com cerca de um bilhão de vértices, cada um dos quais está conectado a cerca de 100 outros vértices aleatoriamente.

Quero encontrar o comprimento do caminho mais curto entre dois pontos. Eu não me importo com o caminho real usado.

Notas:

• Às vezes, as arestas serão cortadas ou adicionadas. Isso acontece cerca de 500 vezes menos que as pesquisas. Também é aceitável alterar alterações de borda, caso permita obter melhor desempenho.
• Eu posso pré-processar o gráfico.
• Se demorar mais de 6 etapas, você poderá voltar com o infinito.
• É aceitável estar errado em 0,01% do tempo, mas apenas ao retornar um comprimento muito longo.
• Todas as arestas têm um comprimento de 1.
• Todas as arestas são bidirecionais.

Estou procurando um algoritmo. Psuedocode, descrições em inglês e código real são ótimos.

Eu poderia usar A *, mas isso parece otimizado para busca de caminhos.
Pensei em usar o algoritmo de Dijkstra , mas ele possui uma etapa que requer a configuração do atributo mais curto encontrado em todos os vértices para o infinito

(Se você está se perguntando sobre o caso de uso, é para o Concurso C Underhanded.)

Algoritmo básico

Mantenha dois conjuntos de nós que você pode alcançar a partir do nó inicial e final. De maneira alternada, dê três passos de ambos os lados. Cada vez que você substitui seu conjunto por nós, você pode alcançar mais uma etapa. Após cada etapa, você verifica os dois conjuntos em busca de nós comuns.

Otimizações

Certifique-se de iterar os conjuntos conforme classificados, para poder procurar nós comuns em uma única varredura: uma operação O (n + m). As listas terão até um milhão de nós cada.

Para estender um conjunto com uma etapa, você deve consultar todas as conexões dos nós no conjunto original e mesclá-las em um novo conjunto classificado. A mesclagem de 2 listas ordenadas pode ser novamente realizada em uma única varredura. Portanto, você também deseja certificar-se de que pode consultar as conexões de um nó conforme classificado. (Isso pode ser pré-processado).

Nas duas últimas etapas, cada novo conjunto é o resultado da mesclagem de até 10000 desses resultados da consulta. É melhor fazer essa mesclagem adaptativa (mesclando pedaços de tamanho igual). Dessa forma, a estrutura de dados do conjunto classificado pode ser uma simples lista vinculada.

Dessa forma, todo o algoritmo se torna O (6 * n + 6 * n * log n) onde n é máximo. 1.000.000.

Basta usar a primeira pesquisa de respiração (não é necessário o alg de Dijkstra. Porque todas as arestas têm comprimento uniforme) (e, como disse Kris Van Bael, execute-a pelos dois lados)

"All edges have a length of 1"Esse é o melhor cenário, tornando o algoritmo de Dijkstra uma escolha perfeita de algoritmo ganancioso. Mesmo usando o algoritmo de Floyd-Warshall, envolvendo a multiplicação rápida de matrizes, funcionaria bem.