Bi Directional Dijkstra
1.0.0
Dado um gráfico com pesos de borda não negativos, um vértice de origem e um vertec de alvo. Encontre o caminho mais curto entre S e T
Mas por que não usamos apenas o algoritmo de Dijkstra para resolver o problema?
0 (E + VLOGV) é a pior complexidade do tempo do algoritmo de Dijkstra, que é muito rápido. Mas, para um gráfico com 20 milhões de vértices e 50 milhões de arestas, ele funcionará por vários segundos, em média. Então, precisamos de algo significativamente mais rápido.
Antes de entrarmos nos detalhes da busca bidirecional, vamos explorar o conceito de "seis graus de separação"
- Em 1929, um autor húngaro, Frigyes Karinthy, propôs pela primeira vez o conceito de "seis graus de separação" em suas cadeias de conto.
- Seis graus de separação são a idéia de que todos os seres vivos e tudo o mais no mundo estão a seis ou menos passos de distância um do outro.
Agora, vamos olhar para a rede social mais popular, o Facebook. Suponha que uma pessoa comum no Facebook tenha cerca de 100 amigos. Então, se considerarmos amigos de amigos dessa pessoa, serão 100*100 que são 10.000 amigos de amigos. Se considerarmos "amigos de amigos dos amigos" , isso será 100 vezes mais ou 1 milhão. E se continuarmos que seis vezes teremos 1 trilhão de pessoas.
Mas, a população global é de 7,6 bilhões.
Agora, como encontramos o caminho mais curto entre as duas pessoas aleatórias A e B por meio de suas conexões na rede social?
Vamos considerar a pesquisa bidirecional. Portanto, consideraremos amigos de amigos de amigos de A e amigos de amigos de amigos de B. Se o conceito de seis graus de separação for verdadeiro, haverá uma pessoa comum entre amigos de amigos de amigos de A e amigos de amigos de amigos de B. Então podemos encontrar facilmente o caminho mais curto que conecta a e B.
Observe que teremos aproximadamente 1 milhão de amigos de amigos de amigos para A e B. Portanto, no total consideraremos apenas 2 milhões de pessoas neste caso.
O algoritmo normal de Dijkstra teria que procurar cerca de 2 bilhões de pessoas na rede social para encontrar o caminho mais curto entre A e B.
Nisso, realizamos duas pesquisas simultâneas: uma para a frente do estado inicial e uma para trás do gol, parando quando os dois se encontram no meio.
- Build GR (gráfico inverso)
- Inicie Dijkstra de S (fonte) em G e de T (Target) em GR
- Alterne entre as etapas de Dijkstra em G e em GR
- Pare quando algum vértice "V" é processado em G e Gr.
- Calcule o caminho mais curto entre S e T.
Computação do caminho mais curto entre s e t: Seja dist [u] a estimativa de distância no dijkstra direto de s em g. Seja distr [u] a estimativa de distância no dijkstra atrasado de t em gr. Depois que algum nó "V" é processado em G e GR, algum caminho mais curto de S para T passa por algum nó "U" que é processado em G, em GR ou ambos e D (S, T) = dist [u] + distr [u]
