Алгоритм нахождения максимального потока в сети

Алгоритм определения возможности насыщения сети распределения товаром направлен на определение объемов поставок товара в звенья распределительной системы при учете возможностей дальнейшего продвижения товара по звеньям сети и пропускной способности этих звеньев. Расчет проводится на основе следующего алгоритма.

  • 1. Установить значения отметок всех вершин орграфа, за исключением а, равными «—».
  • 2. Установить резерв вершины а равным <*>.
  • 3. Включить а в S: S = {а}.
  • 4. Если S — пустое множество, идти к 28, иначе — к шагу 5.
  • 5. Если S не является пустым множеством, выбрать элемент множества S, имеющий максимальный приоритет в матрице предпочтений.
  • 6. Обозначить выбранный элемент v.
  • 7. Удалить выбранный элемент из множества S.
  • 8. Если у v есть неотмеченные последующие вершины, идти к шагу 9, иначе — к шагу 17.
  • 9. Выбрать последующую v неотмеченную вершину, имеющую максимальный приоритет в матрице предпочтений.
  • 10. Обозначить выбранную вершину w.
  • 11. Если/((v,w)) < c((v,w)), идти к шагу 12, иначе — к шагу 16.
  • 12. Рассчитать резерв вершины w: Rw = min {c((v,w)) — .A(v,w));

Rv}.

  • 13. Обозначить предшествующую w вершину.
  • 14. Если w Ф z, идти к шагу 15, иначе — к шагу 25.
  • 15. Добавить w в S.
  • 16. Все последующие v неотмеченные вершины рассмотрены? Если да, идти к 17, иначе — к шагу 9.
  • 17. Если у вершины v есть неотмеченные предшествующие вершины, идти к 18, иначе — к шагу 4.
  • 18. Выбрать предшествующую v неотмеченную и ранее не просмотренную вершину, имеющую максимальный приоритет в матрице предпочтений.
  • 19. Обозначить выбранную вершину w.
  • 20. Если/((v,w)) > 0 идти к шагу 21, иначе — к шагу 24.
  • 21. Рассчитать резерв вершины w: Rw = min {/((v,w)); Rv}.
  • 22. Обозначить предшествующую w вершину.
  • 23. Добавить w в S.
  • 24. Все предшествующие v неотмеченные вершины рассмотрены? Если да, идти к 4, иначе — к шагу 18.
  • 25. Используя отметки предшествующих вершин, построить цепь от z к а.
  • 26. Для построенной цепи от z к а увеличить величину потока каждого ребра, ориентированного по направлению от а к z, на резерв вершины z и уменьшить величину потока каждого ребра, ориентированного по направлению от z к а, на резерв вершины z-
  • 27. Идти к шагу 1.
  • 28. Конец.

Блок-схема алгоритма представлена на рис. 13.5.

Блок-схема алгоритма метода максимального потока

Рис. 13.5. Блок-схема алгоритма метода максимального потока

(окончание)

Рис. 13.5 (окончание)

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >