Confused para escolher o caminho mais curto desde a sua localização até ao destino… Então, você deve saber sobre este algoritmo.
- Floyd-Warshall’s Algorithm é usado para encontrar os caminhos mais curtos entre todos os pares de vértices em um gráfico, onde cada borda no gráfico tem um peso que é positivo ou negativo.
- A maior vantagem de usar este algoritmo é que todas as distâncias mais curtas entre quaisquer 2 vértices podem ser calculadas em O(V3), onde V é o número de vértices num gráfico.
- O algoritmo Floyd-Warshall também é chamado de algoritmo Floyd’s, algoritmo Roy-Floyd, algoritmo Roy-Warshall, ou algoritmo WFI.
- Este algoritmo segue a abordagem de programação dinâmica para encontrar os caminhos mais curtos.
Algoritmo
Para um gráfico com N vértices:
Passo 1: Inicialize os caminhos mais curtos entre quaisquer 2 vértices com Infinity.
Passo 2: Encontre todos os pares de caminhos mais curtos que usam 0 vértices intermediários, depois encontre os caminhos mais curtos que usam 1 vértice intermediário e assim por diante… até usar todos os N vértices como nós intermediários.
Passo 3: Minimizar os caminhos mais curtos entre quaisquer 2 pares na operação anterior.
Passo 4: Para quaisquer 2 vértices (i,j) , deve-se realmente minimizar as distâncias entre este par usando os primeiros nós K, então o caminho mais curto será: min(dist+dist,dist).
dist representa o caminho mais curto que usa apenas os primeiros vértices K, dist representa o caminho mais curto entre o par k,j. Como o caminho mais curto será uma concatenação do caminho mais curto de i a k, então de k a j.
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
dist = min( dist, dist + dist );
}
}
}
Exemplo
Deixe o gráfico dado ser:
Seguir os passos abaixo para encontrar o caminho mais curto entre todos os pares de vértices.
- Criar uma matriz
A0de dimensãon*nonde n é o número de vértices. A linha e a coluna são indexadas como i e j respectivamente. i e j são os vértices do gráfico.
Cada célula A é preenchida com a distância do vértice ith até ao vértice jth. Se não houver caminho de ith vértice para jth vértice, a célula é deixada como infinito.
2. Agora, crie uma matriz A1 usando matriz A0. Os elementos da primeira coluna e da primeira linha são deixados como estão. As restantes células são preenchidas da seguinte forma.
Deixe k ser o vértice de congelamento no caminho mais curto desde a origem até ao destino. Neste passo, k é o primeiro vértice.A é preenchido com (A + A) if (A > A + A).
Isto é, se a distância direta da fonte até o destino for maior que o caminho através do vértice k, então a célula é preenchida com A + A.
Neste passo, k é o vértice 1. Calculamos a distância do vértice fonte até o vértice destino através deste vértice k.
Por exemplo: Para A1, a distância direta do vértice 2 ao 4 é 4 e a soma da distância do vértice 2 ao 4 através do vértice (isto é, do vértice 2 ao 1 e do vértice 1 ao 4) é 7. Como 4 < 7, A0 é preenchido com 4.
3. De forma semelhante, A2 é criado usando A3. Os elementos da segunda coluna e da segunda linha são deixados como estão.
Neste passo, k é o segundo vértice (isto é, vértice 2). Os demais passos são os mesmos do passo 2.
4. Da mesma forma, A3 e A4 também é criado.
>
>
>
>>>
>
>
>
>
>
>A4 dá o caminho mais curto entre cada par de vértices.
Confused para seleccionar o caminho mais curto, depois use o código abaixo para o encontrar. Mas digite as distâncias corretas.
Complexidade de Tempo
Existem três loops. Cada laço tem complexidades constantes. Então, a complexidade temporal do algoritmo Floyd-Warshall é O(n3).
Complexidade Espacial
A complexidade espacial do algoritmo Floyd-Warshall é O(n2).