Algoritmo de floy

Programación de operaciones

ALGORITMO DE FLOYD

El algoritmo de Floyd es un algoritmo en el cual en un grafo por medio de interacciones y de pasos va demostrándonos los valores en peso con los cuales interactúan uno con otro, al mostrarnos todas las interacciones podemos saber al final cual es el camino más corto de un nodo origen a unnodo destino.

A continuación una muestra de este algoritmo

2

3
4
1
4 1
5
1
2 2

Vamos a aplicar el algoritmo en el sig. Grafo
Creamos una tabla en la cual vamos a ver las interacciones de los grafos en una las distancias y en otra los recorridos la diagonal central siempre va vacía y después se empieza a capturar los datos iniciales
Ponemos en cada uno delos campos las distancias las cuales pesan de un grafo a otro
| 1 | 2 | 3 | 4 |
1 | - | 4 | 2 | 5 |
2 | 4 | - | & | 1 |
3 | 2 | 1 | - | 2 |
4 | 5 | 1 | 2 | - |

Después en la sig.tabla marcamos las interacciones
| 1 | 2 | 3 | 4 |
1 | - | 2 | 3 | 4 |
2 | 1 | - | 3 | 4 |
3 | 1 | 2 | - | 4 |
4 | 1 | 2 | 3 | - |
En la primera interaccióntenemos que ver lo que no estasombreado cada uno de los espacios si es menor a la suma de los puntos sombreados que dan a su coordenada en este caso el infinito de campo (2,3) es mayor a la suma de sus coordenadas que da a seis y se suple y en la segunda tabla marcamos que en la primera interacción cambio ese punto
| 1 | 2 | 3 | 4 |
1 | - | 4 | 2 | 5 |
2 | 4 | - | &/6 | 1 |
3 | 2 | 1 | - | 2 |
4 | 5 | 1 | 2 | - || 1 | 2 | 3 | 4 |
1 | - | 2 | 3 | 4 |
2 | 1 | - | 3/1 | 4 |
3 | 1 | 2 | - | 4 |
4 | 1 | 2 | 3 | - |

En la primera interacción es el primer cambio y así se siguen realizando las sig. Interacciones

INTERACCION DOS
En este paso no cambio ninguna
| 1 | 2 | 3 | 4 |
1 | - | 4 | 2 | 5 |
2 | 4 | - | &/6 | 1 |
3 | 2 | 1 | - | 2 |
4 | 5 | 1 | 2 | - |

| 1 | 2 | 3 | 4 |
1| - | 2 | 3 | 4 |
2 | 1 | - | 3/1 | 4 |
3 | 1 | 2 | - | 4 |
4 | 1 | 2 | 3 | - |

INTERACCION TRES
| 1 | 2 | 3 | 4 |
1 | - | 4/3 | 2 | 5/4 |
2 | 4 | - | &/6 | 1 |
3 | 2 | 1 | - | 2 |
4 | 5/4 | 1 | 2 | - |

| 1 | 2 | 3 | 4 |
1 | - | 2/3 | 3 | 4/3 |
2 | 1 | - | 3/1 | 4 |
3 | 1 | 2 | - | 4 |
4 | 1/3 | 2 | 3 | - |

INTERACCION CUATRO
| 1 | 2 | 3 | 4 |
1 | - |4/3 | 2 | 5/4 |
2 | 4 | - | &/6/3 | 1 |
3 | 2 | 1 | - | 2 |
4 | 5/4 | 1 | 2 | - |

| 1 | 2 | 3 | 4 |
1 | - | 2/3 | 3 | 4/3 |
2 | 1 | - | 3/1/4 | 4 |
3 | 1 | 2 | - | 4 |
4 | 1/3 | 2 | 3 | - |

Al terminar los pasos nos queda la siguiente tabla
ESTA ES LA TABAL DE DISTANCIAS
| 1 | 2 | 3 | 4 |
1 | - | 3 | 2 | 4 |
2 | 4 | - | 3 | 1 |
3 | 2 | 1 | - | 2 |
4 | 4 | 1 |2 | - |

ESTA ES LA TABLA DE RECORRIDOS
| 1 | 2 | 3 | 4 |
1 | - | 3 | 3 | 3 |
2 | 1 | - | 4 | 4 |
3 | 1 | 2 | - | 4 |
4 | 3 | 2 | 3 | - |

YA CON NUESTRAS TABLAS PODEMOS OBTENER LOS RECORRIDOS QUE QUERAMOS POR EJEMPLO
LA DISTANCIA DE DOS A TRES ES 3 YA QUE VEMOS EN LA TABLA DE ARRIBA
Y PARA LLEGAR A EL VEMOS EN LA TABAL DE ABAJO QUE PARA LLEGAR DE DOS A TRES TENEMOS QUE EMPESAREN DOS PASAR POR CUATRO Y LLEGAR A TRES.

ALGORITMO DE Dijkstra

El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista. Su nombre se refiere a EdsgerDijkstra, quien lo describió porprimera vez en 1959.

La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene. El algoritmo es una especialización de la búsqueda de costo uniforme, y como...