Algoritmo de Busacker Gowen

Algoritmo de Busacker Gowen

También conocido como algoritmo de Roy, el algoritmo de Busacker Gowen le permite calcular un flujo máximo a un costo mínimo.

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

El algoritmo se resume de la siguiente manera:

  • Construya un gráfico de pcc (ruta más corta) a partir 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

Compartir, repartir
es_ESES
A los bloggers de %d les gusta esto: