Помогите решить 2 задачки:)

truf

Задачка1

Задачка2

shpanenoc

Про алгоритм Форда не слышал, в Кормене не видел. Есть алгоритм Форда-Фалкерсона поиска максимального потока, но тогда возникает вопрос: зачем для простой задачи поиска кратчайшего пути применять модификацию сложного метода поиска оптимального потока?
2. Добавим вершину-источник A, из нее дуги A-A1, A-A2, A-A3 с пропускными способностями, равными запасам, вершину-сток B и дуги B1-B, B2-B, B3-B с пропускными способностями, равными потребностям, а затем решать задачу о максимальном потоке из A в B методом того же Форда-Фалкерсона. Если надо подробнее, могу описать.

truf

видимо в первой задачке речь идет об алгоритме Форда Беллмана, я точно не знаю:
алгоритм Форда Беллмана Wiki
а вторую поподробнее, если нетрудно :)

kinglion

http://elib.hackers/books/12766
Кормен Т., Лейзерсон Ч., Ривест Р. — Алгоритмы: построение и анализ, Глава VI.
Оба алгоритма подробно изложены.
Оставить комментарий
Имя или ник:
Комментарий: