Algoritmo de Busacker Gowen

Algoritmo de Busacker Gowen

También conocido como algoritmo de Roy, el algoritmo de Busacker Gowen calcula un flujo maximo al mínimo costo.

El principio es simple, la búsqueda de la trayectoria creciente se realiza mediante un cálculo de camino más corto (ruta de menor costo). Los criterios de optimalidad son equivalentes al problema de flujo.

El algoritmo se resume de la siguiente manera:

  • Construir un grafico de pcc (camino más corto) del gráfico de desviación de flujo
    • arco idéntico al gráfico de desviación
    • precio correspondiente al arco original si está en la misma dirección; de lo contrario, invierte
  • Busque un pcc de la sa la t
    • si existe, es el camino creciente, el saturado y volver al paso anterior
    • si no hay ruta, fin del algoritmo.

algoritmo de busacker gowen algoritmo de roy flujo de flujo de costo mínimo máximo flujo de costo mínimo

Compartir, repartir