Нахождение пути между пунктами

Нахождение пути между пунктами, Нужно построить (в таблице) возможные пути между выбранными пунктами

Пользователь

Сообщений: 8 Регистрация: 01.01.1970

04.10.2013 21:14:19

Доброго времени суток уважаемые форумчане!
Нужна Ваша помощь в решении следующей задачи:
Есть сеть дорог между пунктами (заданы отрезками в виде списка и в виде матрицы). Выбирая в ячейках В2 и С2 пункты отправления и назначения - в ячейках D2 и E2 нужно получить протяженность и время в пути (наименьший из возможных по времени). Для проверки необходимо видеть из чего он сложился (таблица В5:Е17).
Решить данную задачи через Надстройку "Подбор параметра" не выходит, так как получается превышение по максимально возможным параметрам.
Видел на данном сайте оригинальное решение от Владимира про дорогу из Днепропетровска в Киев - но там есть важный нюанс - четко задано начало и конец поездки и под это построена матрица.
Изучение в течении недели Интернета пишет что это классический случай который легко решается алгоритмом Дейкстры и даже полно ссылок на коды программ на С++ и паскале и прочих. Решения в Excele данной проблемы не нашел (Подбор параметра не в счет).
Есть серьезные подозрения что я далеко не первый кто озадачился данной проблемой. Возможно есть решения на VBA. Прошу поделится опытом кто уже сталкивался с данной задачей и как ее решал. Если есть еще какие мысли прошу подсказать

Прикрепленные файлы

ПримерМаршруты.rar (25.26 КБ)

iba2004 Пользователь Сообщений: 1034 Регистрация: 22.12.2012	#2 05.10.2013 23:31:20 Вы логистикой занимаетесь?

Vasilijc

Пользователь

Сообщений: 8 Регистрация: 01.01.1970

06.10.2013 10:45:45

Доброго времени суток iba 2004
Профессионально логистикой не занимаюсь. Есть желание построить работоспособную модель по управлению грузопотоками, для этого необходимо находить оптимальный маршрут.
Есть простой вариант, но не гибкий и довольно долгий - описать все маршруты вручную. Если не найду решения придется на нем остановиться.

MCH

Пользователь

Сообщений: 3906 Регистрация: 22.12.2012

06.10.2013 17:18:17

Реализовал алгоритмом Форда-Беллмана (кода получилось много, лень оптимизировать)
Алгоритм Дейкстры или алгоритм Левита тоже реализуем, но пока не придумал, как хранить граф

Прикрепленные файлы

FordBellman.xls (62.5 КБ)

Изменено: MCH - 06.10.2013 17:25:38

Rustem

Пользователь

Сообщений: 520 Регистрация: 16.01.2013

06.10.2013 18:06:10

Плохо искали. Посмотрите здесь:
http://en.giswiki.org/wiki/Dijkstra%27s_algorithm#Visual_Basic_6
и вот этот файл на формулах...
Отпишитесь, работает ли приведенный код. Сам с VBA на "Вы".

Прикрепленные файлы

DijkstraAlgorithmGraphMinimalWeightedDistance120428.rar (18.54 КБ)

Изменено: Rustem - 06.10.2013 18:44:35

Excel 2013

Vasilijc

Пользователь

Сообщений: 8 Регистрация: 01.01.1970

06.10.2013 18:53:22

Уважаемые MCH и Rustem!
Спасибо что уделили время, информации много буду разбираться. МСН отдельное спасибо за подробный комментарий в программе так, как в VBA я слабоват (пользуюсь в основном макрорекодером). Попробую еще вариант от Rustem формулами, как осмыслю отпишусь сюда, если получиться решить свой пример через формулы выложу сюда, может еще кто искать будет.

MCH Пользователь Сообщений: 3906 Регистрация: 22.12.2012	#7 08.10.2013 16:59:02 Реализовал Алгоритм Дейкстры, под текущую задачу Прикрепленные файлы MyDijkstra.xls (89 КБ)

Vasilijc

Пользователь

Сообщений: 8 Регистрация: 01.01.1970

09.10.2013 20:31:52

Доброго времени суток МСН!
Огромное спасибо за Ваше решение, да и еще двумя способами! Если честно не ожидал. Буду разбираться в коде. На мой взгляд многим может пригодиться что студентам графы обсчитывать, что логистам транспортные потоки сравнивать.
П.С. для "чайников" решение через UDF - это пользовательская функция MyDiyrstra, или там еще что то где то спрятано?

MCH

Пользователь

Сообщений: 3906 Регистрация: 22.12.2012

10.10.2013 07:54:52

Дополнил решение алгоритмом Левита, а также прокомментировал код.
Описание алгоритмов взял здесь http://e-maxx.ru/algo/

Решение макросом и через UDF (макрос также ссылается на UDF), но т.к. UDF (пользовательская функция) возвращает массив, возникает ошибка #Н/Д в ячейках, где нет данных, возможно не очень удобно будет пользоваться

Прикрепленные файлы

Dijkstra+Levit+FordBellman.rar (43.82 КБ)

Изменено: MCH - 10.10.2013 13:08:07

Vasilijc

Пользователь

Сообщений: 8 Регистрация: 01.01.1970

#10

12.10.2013 21:13:34

Доброго времени суток МСН!
Поражаюсь Вашей работоспособностью!
Извиняюсь за ответы с опозданием, пока не каждый день до компа добираюсь. То что н/д выдает я думаю можно будет побороть. Михаил может пора надстройку свою делать?

Отдельное огромное спасибо за подробные комментарии, даже я далекий от VBA почти все понял

, правда сам пока не повторю.... Буду смотреть вариант, которым удобнее считать.

MCH Пользователь Сообщений: 3906 Регистрация: 22.12.2012	#11 12.10.2013 23:10:04 Сделал еще одно решение: алгоритм Дейкстры для разреженного графа решение разместил на другом форуме http://www.excelworld.ru/forum/3-6656-1 Если будут еще варианты, то буду размещать там

Vasilijc Пользователь Сообщений: 8 Регистрация: 01.01.1970	#12 13.10.2013 20:07:08 Доброго времени суток МСН! А ссылка рабочая? Не могу туда попасть, просьба проверьте пожалуйста.

RAN Пользователь Сообщений: 7207 Регистрация: 21.12.2012	#13 13.10.2013 21:27:00 Ссылка, думаю, рабочая, но сайт висит...

Vl Vl Пользователь Сообщений: 8 Регистрация: 26.07.2020	#14 20.09.2020 18:42:08 Приветствую! У меня вопрос - предложенное решение может быть использовано для поиска не одного, а нескольких кратчайших маршрутов? Т.е. есть самый короткий и к нему найти ещё определенное (заданное) количество, по возрастанию расстояния. Может быть интересным рассмотреть все возможные маршруты между двумя точками, но уж больно много их может быть.