Qual é o algoritmo mais rápido para encontrar todos os caminhos mais curtos em um gráfico esparso?

24

Em um gráfico não ponderado, não direcionado, com vértices V e arestas E modo que 2V>E , qual é a maneira mais rápida de encontrar todos os caminhos mais curtos de um gráfico? Isso pode ser feito mais rápido que o Floyd-Warshall, que é O(V3) mas muito rápido por iteração?

E se o gráfico for ponderado?

Jakob Weisblat
fonte

Respostas:

32

Como este é um gráfico não ponderado, você pode executar uma BFS ( Largura da Primeira Pesquisa ) de todos os vértices do gráfico. Cada execução do BFS fornece as distâncias (e caminhos) mais curtos do vértice inicial para todos os outros vértices. A complexidade de tempo para um BFS é O ( V + E ) = O ( V ), já que E = O ( V ) em seu gráfico esparso. Executá-lo V vezes fornece um O ( V 2vO(V+E)=O(V)E=O(V)V complexidade de tempo.O(V2)

Para um gráfico direcionado ponderado, o algoritmo de Johnson, conforme sugerido por Yuval, é o mais rápido para gráficos esparsos. É preciso que, no seu caso, acaba por ser O ( V 2 log V ) . Para um gráfico não direcionado ponderado, você pode executar o algoritmo de DijkstraO(V2registroV+VE)O(V2registroV)de cada nó ou substitua cada aresta não direcionada por duas arestas direcionadas opostas e execute o algoritmo de Johnson. Ambos fornecerão os mesmos tempos assintóticos do algoritmo de Johnson acima para o seu caso escasso. Observe também que a abordagem BFS mencionada acima funciona para gráficos direcionados e não direcionados.

Paresh
fonte
7

Existe o algoritmo de Johnson , cujo tempo de execução é .O(V2registroV+VE)

Yuval Filmus
fonte
7

Você pode tentar criar uma versão do Floyd-Warshall mais rápida em matrizes esparsas.

Primeiro, vamos relembrar o que esse algoritmo faz:

Seja uma matriz de distâncias. No início do algoritmo M i , j é o peso da aresta i j . Se essa aresta não existir, então M i , j = MMEu,jEujMEu,j= .

O algoritmo possui etapas. Na etapa k do algoritmo, para cada par de nós i , j , definimosVkEu,j

MEu,jmin{MEu,j,MEu,k+Mk,j}.

Claramente, se ou M k , j = , nenhuma atualização precisa ser executada. Assim, nos primeiros passos do algoritmo, precisamos apenas de executar cerca de d e g i n ( k ) d e g o u t ( k ) comparações onde d e g i n ( k ) e d e g o u t (MEu,k=Mk,j=degEun(k)degovocêt(k)degEun(k)são preenchidas. Portanto, os últimos passos podem levar muito mais tempo. denotam o número de arestas de entrada e saída do k- ésimo nó, respectivamente. À medida que o algoritmo progride, mais e mais entradas da matriz Mdegovocêt(k)kM

Observe que precisamos de uma maneira eficiente de iterar apenas células não-infinitas no k ésima linha e coluna da matriz. Isso pode ser feito mantendo um conjunto de arestas de entrada e saída para cada nó.

E=O(V)k=0 0O(1)MO(V)k=|V|O(V2)O(V3)

Amit Moscovich
fonte