Algoritmo de Floyd Warshall

¿Estás confundido a la hora de elegir el camino más corto desde tu ubicación hasta el destino? Entonces, debes conocer este algoritmo.

• El Algoritmo de Floyd-Warshall se utiliza para encontrar los caminos más cortos entre todos los pares de vértices de un gráfico, donde cada arista del gráfico tiene un peso que es positivo o negativo.
• La mayor ventaja de utilizar este algoritmo es que todas las distancias más cortas entre 2 vértices cualesquiera pueden calcularse en O(V3), donde V es el número de vértices de un grafo.
• El algoritmo de Floyd-Warshall también se denomina algoritmo de Floyd, algoritmo de Roy-Floyd, algoritmo de Roy-Warshall o algoritmo WFI.
• Este algoritmo sigue el enfoque de programación dinámica para encontrar los caminos más cortos.

Algoritmo

Para un grafo con N vértices:

Paso 1: Inicializar los caminos más cortos entre 2 vértices cualesquiera con Infinito.

Paso 2: Encontrar todos los caminos más cortos pares que utilizan 0 vértices intermedios, luego encontrar los caminos más cortos que utilizan 1 vértice intermedio y así sucesivamente.. hasta utilizar todos los N vértices como nodos intermedios.

Paso 3: Minimizar los caminos más cortos entre 2 pares cualesquiera en la operación anterior.

Paso 4: Para 2 vértices cualesquiera (i,j) , en realidad hay que minimizar las distancias entre este par utilizando los primeros K nodos, por lo que el camino más corto será: min(dist+dist,dist).

dist representa el camino más corto que sólo utiliza los primeros K vértices, dist representa el camino más corto entre el par k,j. Como el camino más corto será una concatenación del camino más corto de i a k, luego 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 );
}
}
}

Ejemplo

Sea el grafo dado:

Siga los pasos siguientes para encontrar el camino más corto entre todos los pares de vértices.

1. Crear una matriz A0 de dimensión n*n donde n es el número de vértices. La fila y la columna se indexan como i y j respectivamente. i y j son los vértices del grafo.

Cada celda A se rellena con la distancia del vértice ith al vértice jth. Si no hay camino desde el vértice ith al vértice jth, la celda se deja como infinita.

2. Ahora, crea una matriz A1 utilizando la matriz A0. Los elementos de la primera columna y la primera fila se dejan como están. Las celdas restantes se rellenan de la siguiente manera.

Sea k el vértice de congelación en el camino más corto del origen al destino. En este paso, k es el primer vértice.A Se rellena con (A + A) if (A > A + A).

Es decir, si la distancia directa del origen al destino es mayor que el camino que pasa por el vértice k, entonces la celda se rellena con A + A.

En este paso, k es el vértice 1. Calculamos la distancia del vértice de origen al vértice de destino a través de este vértice k.

Por ejemplo: Para A1, la distancia directa del vértice 2 al 4 es 4 y la suma de la distancia del vértice 2 al 4 a través del vértice (es decir, del vértice 2 al 1 y del vértice 1 al 4) es 7. Como 4 < 7, A0 se rellena con 4.

3. De forma similar, A2 se crea utilizando A3. Los elementos de la segunda columna y la segunda fila se dejan como están.

En este paso, k es el segundo vértice (es decir, el vértice 2). Los pasos restantes son los mismos que en el paso 2.

4. Del mismo modo, también se crea A3 y A4.

A4 da el camino más corto entre cada par de vértices.

Configurar el camino más corto, a continuación, utilizar el código de abajo para encontrarlo. Pero introduce las distancias correctas.

Complejidad temporal

Hay tres bucles. Cada bucle tiene complejidades constantes. Así, la complejidad temporal del algoritmo de Floyd-Warshall es O(n3).

Complejidad espacial

La complejidad espacial del algoritmo de Floyd-Warshall es O(n2).