O melhor algoritmo de caminho mais curto

Question

Qual é a diferença entre o "algoritmo de Floyd-Warshall" e "Algoritmo de Dijkstra" , e qual é o melhor para encontrar o caminho mais curto em um gráfico?

Eu preciso calcular o caminho mais curto entre todos os pares em uma rede e salvar os resultados para uma matriz da seguinte forma:

**A     B     C     D      E**
A 0     10    15    5     20
B 10     0    5     5     10
C 15     5    0     10    15
D 5      5    10    0     15
E 20     10    15   15    0

Answer 1

Dijkstra 's algoritmo encontra o caminho mais curto entre um nó e todos os outros nós no o gráfico. Você iria executá-lo uma vez para cada nó. Pesos devem ser não-negativo, por isso, se necessário você tem que normalizar os valores no gráfico pela primeira vez.

Floyd-Warshall calcula os percursos mais curtos entre todos os pares de nós em uma única corrida! pesos ciclo deve ser não negativo, e o gráfico deve ser dirigido (o diagrama não é).

Johnson 's algoritmo é usando o algoritmo de Dijkstra para encontrar todos os pares em um passagem única, e é mais rápido para árvores esparsas (veja o link para análise).

Answer 2

Floyd Warshall encontrar os caminhos entre todos os pares de vértices, mas Dijkstra só encontra o caminho de um vértice para todos os outros.

Floyd Warshall é O (| V | ³ ) e Dikstra é O (| E | + | V | log | V |), mas você vai ter que executá-lo V vezes para encontrar tudo pares que dá uma complexidade em O (| E * V | + | V ² | log | V |) I supor. Isto significa que é, possivelmente, mais rápido usar Dijsktra repetidamente que o algoritmo FW, gostaria de tentar ambas as abordagens e ver qual é o mais rápido no caso real.

Answer 3

Dijkstra encontra o caminho mais curto a partir de apenas um vértice, Floyd-Warshall encontra-o entre todas deles.

Answer 4

Use o Floyd-Warshall algoritmo se você quiser encontrar o caminho mais curto entre todas pares de vértices, já que tem um tempo (agora) em execução mais elevada do que o algoritmo de Dijkstra.

O algoritmo de Floyd-Warshall tem um pior desempenho caso de O (| V | ³ ), onde, como Dijkstra tem um desempenho pior caso de O (| E | + | V | log | V |)

Answer 5

Dijkstra é principalmente para o único par mais curto conclusão caminho isto é a partir de um nó para todos os outros nós, onde como Floyd-Warshall é para todos os pares de caminho mais curto isto é, do caminho mais curto entre todos os pares de vértices. O algoritmo de Floyd-Warshall tem um pior desempenho caso de O (| V | 3), onde, como Dijkstra tem um desempenho pior caso de O (| E | + | V | log | V |) Também Dijkstra não pode ser usado para pesos negativos (usamos Bellmann Ford para o mesmo). mas para Floyd-Warshall podemos usar pesos negativos, mas há ciclos negativos

Answer 6

No entretanto melhores algoritmos para o menor problema de caminho única fonte são conhecidos. A uma prática relevante é um derivação do algoritmo de Dijkstra por Torben Hagerup . O algoritmo tem a mesma complexidade de pior caso como Djikstra de, mas no caso da média do tempo de execução esperado é linear no tamanho do gráfico, que é muito mais rápido do que o Dijkstra puro. A idéia do algoritmo é baseado na idéia, que não há necessidade de consultar sempre a borda mínimo da fila. É possível sondagem uma borda da fila, cujo peso é vezes 1+k tão grande como o peso mínimo borda, onde k é algum número maior 0. Mesmo se tal vantagem é escolhido, o algoritmo ainda vai encontrar o caminho mais curto.