Encontrar todos os caminhos mais curtos a partir de cada par de nós em um gráfico

Question

Eu tenho cerca de 70k nós, e 250k bordas, e o gráfico não está necessariamente ligado. Obviamente, usando um algoritmo eficiente é crucial. O que você recomenda?

Como uma nota lateral, eu gostaria de receber conselhos sobre como dividir a tarefa entre várias máquinas -? Isso é possível com este tipo de problema

Graças

Answer 1

Você pode usar o Floyd-Warshall algoritmo . Ele resolve exatamente este problema.

A complexidade é O (V ^ 3).

Há também algoritmo de Johnson com uma complexidade em O (V ^ 2 * log V + VE). Este último também é fácil de distribuir porque ele é executado vezes algoritmo V de Dijkstra, que pode ser feito em paralelo.

Answer 2

MapReduce é um grande algoritmo distribuído para isso, embora possa ser um pouco demasiado alta potência. Se você estiver interessado em que, dê uma olhada este palestra ou talvez este blog para a inspiração. (Na verdade, quando eu fui ensinado MapReduce, este foi um dos primeiros exemplos.)

Para 250k bordas e 70k, parece que o gráfico é relativamente escassa, algoritmo de Dijkstra é executado em O( E + V log V ) para cada nó, para um tempo de execução total (todas as fontes) de O( VE + V^2 log V ). Isso deve ser rápido o suficiente, mas as advertências se aplicam para Dijkstra. (Bordas negativos.)

Você também pode dar uma olhada em de Johnson algoritmo se suas ofertas de problema com negativa pesos, mas não os ciclos negativos. Especificamente, ele também pode ser distribuído, uma vez que leva o gráfico reponderados e corre o algoritmo de Dijkstra de cada nó.

Answer 3

Existem duas maneiras ingênuas de paralelização este problema:
1) Identificar subcomponentes e distribuir estes computadores através diferentes. O comprimento do caminho entre os dois nodos a partir de dois componentes diferentes é indefinido.

2) Coloque o gráfico em computadores diferentes e dar a cada computadores uma lista de nós para calcular todos os caminhos mais curtos. Os resultados para um nó não são dependentes dos resultados de outro nó para que possa paralelizar este problema.

Ao contrário: não muito difícil de implementar, mas eu só iria fazê-lo assim, se você tem que resolver isso de uma vez. Se esta é uma questão recorrente, então você pode querer olhar para algorithsm distribuído.

Use IGRAPH , é escrito em C, muito rápido e você pode usar Python como uma linguagem wrapper.

Answer 4

Look em papéis / publicações que têm as seguintes palavras-chave: distribuído algoritmos de busca gráfico. Aqui 's que podem ser de ajuda.

Há essa conta ACM apenas papel, bem como: computação distribuída em grafos: algoritmos de menor caminho