Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
Форум программистов > Алгоритмы > Реализация транспортной задачи с помощью графа |
Автор: Obsidian 29.10.2009, 00:44 |
Имеется транспортная сеть(буду делать из карты) пользователю нужно будет указать несколько складов и магазинов, задать кол-во товара и потребности. Потом решить транспортную задачу где стоимость доставки=длина пути(кратчайший путь),пропускные способности отсутствуют. Читал у седжвика что решение этой задачи выводится из задачи потока минимальной стоимости, но как точно не пойму. Пока что у меня только такой вариант алгоритма вырисовывается: 1. Найти кратчайшие пути от всех магазинов до всех складов. 2. Заносим в матрицу стоимостей и решаем ТЗ методом потенциалов 3. показываем получившиеся пути и результаты. но конечно хотелось бы чтобы это все решалось напрямую из графа, а не через этот костыль. Буду рад любому совету! |
Автор: _OdinO4ka_ 31.10.2009, 14:01 |
Не знаю насколько может быть актуально или нет, но есть книжка Шишкин, Шишкина Исследование операций, в ней очень хорошо описана данная задача и как она должна представляться для программы, если не найдешь, то пиши в личку скину тебе на почту. |