Algoritmo de Dijkstra & Floyd

 

Algoritmo de Dijkstra.

 

 

Este algoritmo encuentra el camino más corto de un vértice elegido a cualquier otro vértice del grafo, donde la longitud del camino es la suma de los pesos de las aristas que lo forman. Las aristas deben tener peso no negativo. Una posible aplicación de este algoritmo se presenta cuando se desea encontrar la ruta más corta entre 2 ciudades.

 

 

A continuación se presenta el seguimiento del algoritmo de Dijkstra:

S = Arreglo en el que se almacena en cada paso del algoritmo el vértice seleccionado

D[n] = Muestra el valor mínimo del camino encontrado entre el vértice origen y cada uno de los otros vértices.

 

 

Algoritmo de Floyd.

 

 

Este algoritmo encuentra el camino más corto entre todos los vértices del dígrafo.

Sea G = (V, A) donde cada arco u –> v tiene asociado un peso. El algoritmo de Floyd permite encontrar el camino más corto entre cada par ordenado u y v.

La matriz de distancias sirve como punto de partida. Se realizan k iteraciones sobre la matriz buscando el camino más corto, por lo tanto, en la k-ésima iteración, M[i,j] tendrá el camino de menor costo para llegar de i a j, pasando por un número de vértices menor a k, el cual se calculará según la siguiente expresión:

 

 

Se elegirá el camino más corto entre el valor obtenido en la iteración k-1, y el valor que resulta de pasar por el vértice k.

 

 

a) Es la matriz de distancias del digrafo.

b) Es la matriz obtenida usando el vértice B como vértice intermedio. Los caminos encontrados son:

1. A, B, D = 10
2. A, B, E = 6
3. C, B, E = 5

c) Es la matriz obtenida usando el vértice C como vértice intermedio. Se encontró el siguiente camino:

1. E, C, B = 8

d) Es la matriz obtenida usando el vértice E como vértice intermedio. Se encontraron los siguientes caminos:

1. A, E, D = 9
2. B, E, C = 7
3. B, E, D = 5

Esta matriz almacena las distancias mínimas entre cada uno de los vértices del digrafo.