1. Definición del problema:
* red: Estás trabajando con un gráfico dirigido (red) representado por:
* nodos (vértices): `V` (por ejemplo, fábricas, almacenes, ciudades)
* arcs (bordes): `E` (por ejemplo, carreteras, tuberías, enlaces de comunicación)
* Capacidades: Cada arco `(U, V)` en `e` tiene una capacidad` c (u, v) `que representa el flujo máximo que puede pasar a través de él.
* Costos: Cada arco `(u, v)` en `e` tiene un costo` costo (u, v) `representando el costo por unidad de flujo a través de ese arco.
* suministro/demanda: Cada nodo `v` en` v` tiene una oferta `b (v)`.
* Si `b (v)> 0`, el nodo` v` es un * fuente * con un suministro de unidades `b (v)`.
* Si `b (v) <0`, el nodo` v` es un * sumidero * con una demanda de unidades `-b (v)`.
* Si `b (v) =0`, el nodo` v` es un nodo de transbordo.
* Objetivo: Encuentre la asignación de flujo que minimiza el costo total de enviar flujo a través de la red al tiempo que satisface las limitaciones de oferta/demanda y limitaciones de capacidad.
2. Inicialización:
* Red residual: Cree una red residual `G_F` basada en la red original` G`. Inicialmente, `g_f =g`. Esta red realiza un seguimiento de la capacidad disponible. Para cada arco `(u, v)` en `g`, la capacidad residual es` c_f (u, v) =c (u, v) - f (u, v) `, donde` f (u, v) `es el flujo actual en ese arco. Inicialmente, `f (u, v) =0` para todos los arcos.
* flujo: Inicialice el flujo `f (u, v) =0` para todos los arcos en la red original.
* potenciales (precios): Inicializar una función potencial `Pi (V)` para cada nodo `v` en` v`. Un punto de partida común es `pi (v) =0` para todos` v`. Los potenciales son cruciales para manejar ciclos de costos negativos.
3. Pasos de algoritmo:
El núcleo del algoritmo de ruta más corto sucesivo es un proceso iterativo:
a. Encuentra una fuente y un fregadero: Seleccione un nodo fuente `S` (donde` B (S)> 0`) y un nodo de sumidero `T` (donde` B (T) <0`) en la red. Si no existen tales nodos, el algoritmo está completo.
b. Cálculo de ruta más corta: Encuentre la ruta más corta `P` de` S` a `t` en la red residual *` g_f` usando los *costos reducidos *. El costo reducido para un arco `(U, V)` se define como:
`` `` ``
Costo_Reducido (U, V) =Costo (U, V) + PI (U) - PI (V)
`` `` ``
* El objetivo de usar costos reducidos es eliminar los ciclos de costos negativos. Si los potenciales `Pi` se eligen de tal manera que` cost_reduced (u, v)> =0` para todos los arcos, entonces el algoritmo de Dijkstra se puede usar para encontrar la ruta más corta.
* Si los costos negativos permanecen después de aplicar potenciales, se puede usar el algoritmo Bellman-Ford (pero generalmente es más lento).
do. flujo de aumento: Deje que `delta` sea el mínimo de:
* `B (S)` (el suministro restante en la fuente `S`)
* `-B (t)` (la demanda restante en el fregadero `t`)
* La capacidad residual mínima a lo largo de la ruta más corta `P`:` min {c_f (u, v) | (u, v) en p} `
Actualice el flujo a lo largo de la ruta `P` por` Delta`:
* Para cada arco `(U, V)` en `P`:
* `f (u, v) =f (u, v) + delta`
* Actualizar la capacidad residual:`C_f (U, V) =C (U, V) - F (U, V)`
* Si `(U, V)` existe en la red original, actualice su borde inverso en la red residual:cree el borde `(V, U)` en `g_f` si no existe con` c_f (v, u) =f (u, v) `.
d. Actualizar la oferta y la demanda:
* `B (S) =B (S) - Delta`
* `b (t) =b (t) + delta`
mi. ACTUALIZAR POTENCIOS (Variante Bellman-Ford): Este es un paso * crucial * para mantener costos reducidos no negativos y garantizar un comportamiento correcto. Después de aumentar el flujo, debe actualizar los potenciales. Un enfoque común (a menudo utilizado junto con Dijkstra después de un Bellman-Ford inicial) es una variante Bellman-Ford. Esto se puede hacer utilizando las distancias de ruta más cortas de la iteración anterior, pero se aplica en todos los vértices. La clave es asegurarse de que se manejen los ciclos de costo negativos introducidos por el aumento del flujo.
* Opción 1:Full Bellman-Ford (menos eficiente): Vuelva a ejecutar Bellman-Ford de un nodo arbitrario `R` a todos los demás nodos en` G_F` utilizando los costos reducidos. Sea `d (v)` la distancia más corta de `r` a` v`. Actualice los potenciales:`Pi (V) =Pi (V) - D (V)`. Esto garantiza `cost_reduced (u, v)> =0` para todos los arcos después de la actualización, pero es relativamente lento.
* Opción 2:Algoritmo de Johnson (eficiente): Ejecute Bellman-Ford una vez para calcular los potenciales iniciales. Posteriormente, use el algoritmo de Dijkstra utilizando los costos reducidos. Después de cada aumento, recomputa los potenciales utilizando el resultado de Dijkstra.
F. Repetir: Regrese al paso (a) y repita el proceso hasta que se satisfagan todos los suministros y demandas (`b (v) =0` para todos los nodos` v`).
4. Terminación:
El algoritmo termina cuando se satisfacen todos los suministros y demandas. El flujo resultante `f (U, V)` para todos los arcos `(U, V)` en la red original representa el flujo de costos mínimo.
Estructuras de datos clave:
* Lista de adyacencia/matriz: Para representar la red `G` y la red residual` G_F`. Las listas de adyacencia suelen ser más eficientes para gráficos dispersos.
* Matriz de flujo: Para almacenar el flujo de corriente `f (u, v)` en cada arco.
* Matriz de capacidad: Para almacenar las capacidades originales `C (U, V)` de cada arco.
* Matriz de capacidad residual: Para almacenar las capacidades residuales `c_f (u, v)` en la red residual.
* Potencial matriz: Para almacenar los potenciales `Pi (V)` para cada nodo.
* cola prioritaria (montón): Utilizado en el algoritmo de Dijkstra para un cálculo de ruta más corto eficiente.
Consideraciones de código (Ejemplo de Python - Simplificado):
`` `Python
Importar montón
Def sucesive_shortest_path (gráfico, capacidad, costo, suministro):
"" "
Implementa el algoritmo de ruta más corto sucesivo.
Args:
Gráfico:un diccionario que representa el gráfico como una lista de adyacencia.
Las teclas son nodos, los valores son listas de nodos vecinos.
Capacidad:un diccionario que representa la capacidad de cada borde (U, V).
Costo:un diccionario que representa el costo de cada borde (U, V).
Suministro:un diccionario que representa la oferta/demanda de cada nodo.
Los valores positivos son la oferta, los valores negativos son la demanda.
Devoluciones:
Un diccionario que representa el flujo en cada borde, o ninguno si no es una solución factible.
"" "
flujo ={} # Inicializar el flujo a cero
para ti en gráfico:
para v en gráfico [u]:
flujo [(u, v)] =0
potencial ={nodo:0 para nodo en gráfico} # Inicializar potenciales
Mientras que es cierto:
fuentes =[nodo para nodo en suministro si suministro [nodo]> 0]
sumideros =[nodo para nodo en suministro si suministro [nodo] <0]
si no fuentes o no se hunden:
Romper # toda la oferta/demanda satisfecha
fuente =fuentes [0]
sumidero =sumidero [0]
# Ruta más corta usando Dijkstra con costos reducidos
Dist, Prev =Dijkstra (gráfico, capacidad, costo, potencial, fuente, sumidero, flujo)
if dist [federe] ==float ('inf'):# no se encuentra
no devuelve NINGUNA # o manejar este caso de manera diferente
# Flujo de aumento
delta =min (suministro [fuente], -supply [sumidero])
Curr =sumidero
mientras que Curr! =Fuente:
Prev_node =Prev [Curr]
delta =min (delta, capacidad [(prev_node, curr)] - flujo [(prev_node, curr)]))
Curr =prev_node
Curr =sumidero
mientras que Curr! =Fuente:
Prev_node =Prev [Curr]
flujo [(prev_node, curr)] +=delta
if (curr, prev_node) en capacidad:
flujo [(Curr, Prev_node)] -=Delta # Flojo hacia atrás
demás:
flujo [(Curr, Prev_node)] =-Delta # Inicializar si es necesario.
Curr =prev_node
Suministro [fuente] -=Delta
suministro [sumidero] +=delta
# Actualizar potenciales utilizando las distancias de Dijkstra
Para el nodo en gráfico:
potencial [nodo] +=dist [nodo]
flujo de retorno
Def Dijkstra (gráfico, capacidad, costo, potencial, fuente, sumidero, flujo):
"" "
El algoritmo de Dijkstra con costos reducidos.
"" "
dist ={nodo:float ('inf') para nodo en gráfico}
prev ={nodo:ninguno para nodo en gráfico}
dist [fuente] =0
pq =[(0, fuente)] # priority cola (distancia, nodo)
Mientras PQ:
D, U =Heapq.HeAppop (PQ)
Si d> dist [u]:# perezosa eliminación
continuar
para v en gráfico [u]:
# Considere solo bordes con capacidad residual> 0
Si la capacidad [(u, v)] - flujo [(u, v)]> 0:
reducido_cost =costo [(u, v)] + potencial [u] - potencial [v]
if dist [v]> dist [u] + reducido_cost:
dist [v] =dist [u] + reducido_cost
anterior [v] =u
Heapq.HeAppush (PQ, (Dist [V], V))
Distancia de retorno, anterior
Uso de ejemplo:
gráfico ={
's':['a', 'b'],
'a':['b', 't'],
'b':['t'],
'T':[]
}
capacidad ={
('s', 'a'):10,
('s', 'b'):5,
('A', 'B'):4,
('a', 't'):8,
('b', 't'):12
}
costo ={
('s', 'a'):2,
('s', 'b'):4,
('A', 'B'):1,
('a', 't'):7,
('B', 'T'):5
}
suministro ={
's':15,
'A':0,
'B':0,
'T':-15
}
flujo =sucesivo_shortest_path (gráfico, capacidad, costo, suministro)
Si flujo:
Imprimir ("Asignación de flujo:", flujo)
# Calcular el costo total
total_cost =sum (flujo [(u, v)] * costo [(u, v)] para (u, v) en flujo)
Imprimir ("Costo total:", Total_cost)
demás:
Imprimir ("No se encontró una solución factible")
`` `` ``
Consideraciones importantes:
* Ciclos de costos negativos: El algoritmo SSP está diseñado para manejar los ciclos de costos negativos. La función potencial `pi (v)` es crítica para esto. Si no actualiza los potenciales correctamente, el algoritmo no puede converger o puede producir una solución incorrecta.
* Dijkstra vs. Bellman-Ford:
* Si * siempre * mantiene los costos reducidos no negativos, el algoritmo de Dijkstra es mucho más rápido para encontrar caminos más cortos. Este es el escenario ideal y generalmente se logra con actualizaciones potenciales adecuadas.
* Si no puede garantizar costos reducidos no negativos, * debe * usar Bellman-Ford, que es más lento (o (v * e) complejidad del tiempo). A menudo se usa solo para el cálculo potencial inicial.
* Red residual: Mantener la red residual correctamente es esencial. Recuerde crear bordes posteriores cuando se empuja el flujo a lo largo de un arco.
* Complejidad computacional: La complejidad del algoritmo SSP depende del algoritmo de ruta más corto utilizado y del número de iteraciones. En el peor de los casos, puede ser pseudopolinomio si las capacidades son grandes.
* Algoritmos alternativos: Para los problemas de flujo de costos mínimos a gran escala, otros algoritmos como el algoritmo de red simple a menudo son más eficientes.
En resumen, el algoritmo de ruta más corto sucesivo es un método poderoso y conceptualmente claro para resolver problemas de flujo de costos mínimos. Comprender los roles de la red residual, los costos reducidos y la función potencial es clave para implementarlo correctamente. Elija el algoritmo de ruta más corto apropiado (Dijkstra o Bellman-Ford) en función de si puede garantizar costos reducidos no negativos. Recuerde manejar las actualizaciones en la oferta y la demanda y también actualizar los potenciales correctamente.