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

Em um gráfico não ponderado, não direcionado, com vértices $V$ e arestas $E$ modo que $2V \gt 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(V^3)$ mas muito rápido por iteração?

E se o gráfico for ponderado?

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 $v$$O(V + E) = O(V)$$E = O(V)$$V$ complexidade de tempo.$O(V^2)$

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 Dijkstra$O(V^2\log V + VE)$$O(V^2\log V)$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.

Existe o algoritmo de Johnson , cujo tempo de execução é .$O(V^2\log V + VE)$

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 = $M$$M_{i,j}$$i \rightarrow j$$M_{i,j}=\infty$ .

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

$$M_{i,j} \leftarrow \min\{M_{i,j}, M_{i,k}+M_{k,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$M_{i,k}=\infty$$M_{k,j}=\infty$$deg_{in}(k) \cdot deg_{out}(k)$$deg_{in}(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$deg_{out}(k)$$k$$M$

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$$O(1)$$M$$O(V)$$k=|V|$$O(V^2)$$O(V^3)$