Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Реализация транспортной задачи с помощью графа


Автор: Obsidian 29.10.2009, 00:44
Имеется транспортная сеть(буду делать из карты) пользователю нужно будет указать несколько складов и магазинов, задать кол-во товара и потребности. Потом решить транспортную задачу где стоимость доставки=длина пути(кратчайший путь),пропускные способности отсутствуют. Читал у седжвика что решение этой задачи выводится из задачи потока минимальной стоимости, но как точно не пойму.

Пока что у меня только такой вариант алгоритма вырисовывается:
1. Найти кратчайшие пути от всех магазинов до всех складов.
2. Заносим в матрицу стоимостей и решаем ТЗ методом потенциалов
3. показываем получившиеся пути и результаты.

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

Автор: _OdinO4ka_ 31.10.2009, 14:01
Не знаю насколько может быть актуально или нет, но есть книжка Шишкин, Шишкина Исследование операций, в ней очень хорошо описана данная задача и как она должна представляться для программы, если не найдешь, то пиши в личку скину тебе на почту.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)