Publish your project for free and start receiving offers from freelance contractors in serveral minutes after publication!

Визуализация алгоритма Goldberg'а в графе (visual с++)

project expired


Нужно доработать проект, а именно, переделать старый алгоритм в алгоритм Голдберга(поиск максимального потока).


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


В приложенном проекте уже есть матрица смежности по которой заполняется граф, а так же визуализация другого алгоритма, который нужно будет заменить.

(еще небольшая просьба сделать так, чтобы при рандомном заполнении матрицы смежности, элементы были симметричны главной диагонали)


Алгоритм Годберга:

  • Шаг 1. Для каждого ребра (u,v)' tabindex="0">(u,v)(u,v) данной сети G' tabindex="0">GG зададим f(u,v)=0' tabindex="0">f(u,v)=0f(u,v)=0.
  • Шаг 2. Если есть путь из S' tabindex="0">SS в T' tabindex="0">TT — переходим к шагу 3.
  • Шаг 3. Выполняем (1)' tabindex="0">(1)(1) запрос, узкое место и пропускную способность. Если пропускная способность положительна, переходим к шагу 4, иначе к шагу 5.
  • Шаг 4. Улучшение пути. Обновляем значения потока и пропускной способности при помощи (2)' tabindex="0">(2)(2) запроса.
  • Шаг 5. Удаление нулевых ребер. Обрезаем нулевые ребра при помощи (3)' tabindex="0">(3)(3) запроса. Переходим к шагу 2.

Applications 2

Only registered users can view attachments.

  1. proposal withdrawn
  • Oleksandr Ismailov
    18 November at 21:29 |

    Правильно я понимаю вам нужно довести до ума сам алгоритм? И вы хотите чтобы он был написан на С++?

  • Влад Курочкин — project author
    20 November at 14:44 |

    Да, все верно с++ windows form