Поиск кратчайшего пути по алгоритму Флойда-Уоршелла

Скопировать ссылку
Перейти

Скопировать ссылку
Перейти

O(N^3), метода "матричного умножения"

O(Log(K)*N^3), где К - диаметр графа. Множитель Log(K) нивелируется тем, что массовые вычисления в запросе делаются "пакетом" и поэтому быстрее в 10-50 раз. Однако столкнулся с тем, что на схеме метро функция не работает. Насколько я понял, отрезки пути, найденные алгоритмом, не находятся в исходном графе. Прилагаю файл связности станций питерского метро, полученный сохранением в текстовом файле строки, равной ЗначениеВСтрокуВнутр(ТаблицаМаршрутов).

Скопировать ссылку
Перейти

Скопировать ссылку
Перейти

(7) думаю, вы невнимательно прочитали статью , на которую я неоднократно ссылался. Это метод, решающий ту же задачу "All Pairs Shortest Paths (APSP) problem". Так же находятся кратчайшие расстояния между всеми парами вершин. Поэтому сравнивать эти решения можно и нужно.

Проблема в том, что практическая реализация метода, сделанная здесь, пока, на мой взгляд, попросту НЕ РАБОТАЕТ. Вообще не находит путь в графе, пример которого приведен в (6) (вываливается с ошибкой).

Кстати, проблема восстановления кратчайшего пути по кратчайшим расстояниям между всеми парами в статье решается гораздо проще. В кратчайший путь включаются все вершины ПунктПути, обладающие свойством:

Скопировать ссылку
Перейти

Скопировать ссылку
Перейти

(9) ildarovich, все работает

Маршрут считает, что по дням - это с другого более сложного проекта :)

Считал 15 минут потому что 140 станций * 7 дней вершин

Скопировать ссылку
Перейти

(10) я взял функцию из вашей обработки, вставил в свою, получил ошибку (см.скриншоты). - Что я делаю не так?

Отладчик показал, что отрезок пути, который ищется в ТЗМаршруты, там не находится, из-за этого ТекСтр = Неопределено и функция вылетает.

Кстати, создавать колонку поиска было необязательно, достаточно было проиндексировать ТЗ по двум колонкам: тзМаршруты.Индексы.Добавить("СкладОткуда, СкладКуда").

65 станций. 140 - это число связей между станциями.

В общем, хотелось бы разобраться и получить результат сравнения по скорости, не отлаживая самому вашу разработку.

Скопировать ссылку
Перейти

(11) ildarovich, проверял на доработанном алгоритме который умеет считать маршруты между складами когда они не по каждым дням недели ездят. Причем с ожиданием если в этот день недели когда приехали нет маршрутов отправления. для простоты проверил на доработанном, там из екселя как раз загрузка идет, при расчете он каждую вершину (склад, станцию) превращает в 7 по количеству дней в неделе, и даты которые показывает это сколько дней едем и да ошибся не 140*7, а 65*7

насчет ошибки все правильно, восстановление пути для Флойда возможно двумя способами :) http://hci.fenster.name/304y/lab5/ в выложенном сделан ". В этом случае значение массива C[j][k] после окончания алгоритма будет указывать одну из вершин, через которую проходит путь от j к k . " выложенный алгоритм правильно считает кратчайший путь, но не всегда может его восстановить

Скопировать ссылку
Перейти

На примере московского метро примерно на 30% быстрее запроса получается. По ходу дела нашел на ИС статью на смежную тему: Реализация алгоритма Дейкстры . В статье также заявлена и реализация Флойда.

. Ну и еще. Поскольку массив работает быстрее соответствия , попробовал, как и автор, на всякий случай вариант с массивом:

Скопировать ссылку
Перейти

(13) ildarovich, на 30% быстрее получилось потому что соединили алгоритмы Флойда и Дейкстры. И еще потому что вершин и ребер мало. Особенно потому что количество ребер практически равно количеству вершин - линии метро однако.

Попробуйте на 500 вершинах и 5000 ребер? Запрос в этом случае умрет, вариант с соответствием будем в 2-2.5 раза медленнее чем с массивами. Точно будет зависеть от отношения количества вершин к количеству ребер.

Скопировать ссылку
Перейти

Скопировать ссылку
Перейти

Так по опыту собственному и сужу

Какая разница каким образом оптимизировать алгоритм? Алгоритм Дейкстры просматривает ребра (получая из них вершины), обычный Флойда все вершины парами (не важно есть ли между ними ребро).

И да через битовые маски еще быстрее.

Скопировать ссылку
Перейти

Скопировать ссылку
Перейти

(17) ildarovich, понимаете мне это тестирование совершенно неинтересно. Потому что прекрасно понимаю что при разных исходных данных будет разный результат.

Про N^2 это то что вы и сделали по сути. Просто за счет "Если Пути[Узел2.Ключ][Узел1.Ключ] <> Неопределено Тогда" исключили из алгоритма обработку несуществующих ребер. Если число ребер во много раз больше чем число вершин эта доработка за счет лишнего действия (проверка по условию в выниманием значения из структур и сравнение) даст замедление.

А битовые маски это то что и сделали (доп условие перед 3-м циклом) только проверка очень быстрая с помощью бинарных операций. Бинарные операции в 1С реализуемы через числа и деление нацело с остатком (%). http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A 4%D0%BB%D0%BE%D0%B9%D0%B4%D0%B0

ЗЫ при операциях с получением данных из памяти, в случае массива нужное значение (адрес ячейки) получается просто умножением, в случае разных коллекций (в т.ч. структура) используются "ключи" получение данных "по ключу" медленнее, так как нужно преобразовать значение ключа в адрес ячейки со значением но это существенно сказывается только с большими наборами данных

ЗЗЫ еще тонкость с 1С, когда запускают тестирование из "конфигуратора через отладку", и напрямую запускают "режим предприятия" в этом случае отладчик слегка портит результаты

📎📎📎📎📎📎📎📎📎📎