4.3.6. Otros problemas con grafos.
Problemas de flujo en redes
Algoritmo para calcular el flujo máximo.
1. Inicializar un grafo de flujo Gf con los mismos nodos y aristas de G, pero con pesos 0. Este grafo guardará el resultado del algoritmo.
2. Buscar un camino en G, desde s hasta t (camino creciente). Sea m el valor mínimo de los costes de las aristas por las que pasa el camino (por este camino pueden fluir hasta m unidades de flujo).
3. Para cada arista (v, w) del camino, añadir al costo de la arista correspon-diente en Gf el valor m: Cf[v, w] = Cf[v, w] + m.
4. Decrementar el valor m en cada arista (v, w) del camino, en el grafo G. Si la arista toma el valor 0, eliminarla de G.
5. Volver al paso 2 mientras sigan existiendo caminos entre s y t en G.
Ejemplos:
- Caso 1: (s, b, d, t) con m=2; (s, a, c, t) con m=2; (s, a, d, t) con m=1. FIN
- Caso 2: (s, a, d, t) con m=3. FIN
El algoritmo es no determinista y no garantiza una solución óptima.
Solución: en el paso 4 añadir una arista <w, v> a G con costo m (para permitir deshacer los caminos).