PROBLEMA DEL FLUJO MÍNIMO

PROBLEMA DEL FLUJO MÍNIMO

Considere una red conexa y no dirigida con dos nodos especiales llamados origen y destino. A cada ligadura (arco no dirigido) se asocia una distancia no negativa. El objetivo es encontrar la ruta más corta (la trayectoria con la mínima distancia total) del origen al destino.

Se dispone de un algoritmo bastante sencillo para este problema. La esencia del procedimiento es que analiza toda la red a partir del origen; identifica de manera sucesiva la ruta más corta a cada uno de los nodos en orden ascendente de sus distancias (más cortas), desde el origen; el problema queda resuelto en el momento de llegar al nodo destino.

Algoritmo de la ruta más corta:

1. Objetivo de la n-ésima interacción: encontrar el n-ésimo nodo más cercano al origen. (Este paso se repetirá para n=1,2,… hasta que el n-ésimo nodo más cercano sea el nodo destino.)
2. Datos para la n-ésima interacción: n-1 nodos más cercanos al origen (encontrados en las interacciones previas), incluida su ruta más corta y la distancia desde el origen. (Estos nodos y el origen se llaman nodos resueltos, el resto son nodos no resueltos.)
3. Candidatos para el n-ésimo nodo más cercano: Cada nodo resuelto que tiene conexión directa por una ligadura con uno o más nodos no resueltos proporciona un candidato, y éste es el nodo no resuelto que tiene la ligadura más corta. (Los empates proporcionan candidatos adicionales.)
4. Cálculo del n-ésimo nodo más cercano: para cada nodo resuelto y sus candidatos, se suma la distancia entre ellos y la distancia de la ruta más corta desde el origen a este nodo resuelto. El candidato con la distancia total más pequeña es el n-ésimo nodo más cercano (los empates proporcionan nodos resueltos adicionales), y su ruta más corta es la que genera esta distancia.

Después de hacer la diferencia entre el flujo y el requerimiento mínimo se le aplica el algoritmo de ford y fulkerson

Actualizando los flujos en los arcos y haciendo la diferencia entre V1 y V2 se obtiene el flujo mínimo es de 81 del nodo S al T.