Orkut e Dijkstra

Você como bom aluno de Ciência da Computação sabe que Dijkstra é O(n^2), certo? Sabe que para calcular a distância mínima entre todos os vértices é O(n^3): vc pode rodar Dijkstra n vezes ou usar o algoritmo de programação dinâmica do Floyd-Warshall.

Beleza, agora vc, cara esperto, me diga uma coisa: como o Orkutconsegue, de maneira eficiente, me dizer a distância em “pessoa-que-conhece-pessoa-que-conhece…” entre eu e qualquer pessoa que eu buscar, dado o volume de usuários que ele possui? Ele faz isso em batch? Incrementalmente? Como?

Alceu Valença – Morena Tropicana

One Response to “Orkut e Dijkstra”

  1. Betinho says:

    Eu andei pensando nisso que você disse. Atualmente, no Orkut, ele mostra vários caminhos para a pessoa (antes mostrava só um). Pensei primeiro no eficientíssimo algortimo A*, mas não me pareceu uma solução melhor para o caso. Pensei em algo recursivo, partindo das duas pontas. Você poderia procurar se tem caminho, pegando todos os relacionamentos até o nivel 1, já devidamente ordenados, e procurando semelhança por busca binária.

    Sei que foi complicado de dizer, mas é mais fácil de mostrar ao vivo :)

Leave a Reply