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

09.01.16

Разработка - Математика и алгоритмы

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

Скачать файлы

Наименование Файл Версия Размер
FindFloid
.epf 7,62Kb
27
.epf 1.0 7,62Kb 27 Скачать

Алгоритм Флойда — Уоршелла — динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом (англ.), хотя в 1959году Бернард Рой (англ.) (Bernard Roy) опубликовал практически такой же алгоритм, но это осталось незамеченным.


Обработка содержит функцию расчета пути и пример вызова.

В функцию передаётся начальная точка, конечная точка и таблица значений содержащая маршруты между точками с расстоянием между ними.

Таблица значений маршрутов должна содержать 3 колонки: "СкладОткуда", "СкладКуда" и "Расстояние".

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


Пример использования :

тзМаршруты = Новый ТаблицаЗначений;
тзМаршруты.Колонки.Добавить("СкладОткуда");
тзМаршруты.Колонки.Добавить("СкладКуда");
тзМаршруты.Колонки.Добавить("Расстояние");

ДобавитьЗапись(тзМаршруты, "Склад1", "Склад2", 1);
ДобавитьЗапись(тзМаршруты, "Склад1", "Склад3", 2);
ДобавитьЗапись(тзМаршруты, "Склад1", "Склад4", 3);
ДобавитьЗапись(тзМаршруты, "Склад3", "Склад2", 4);
ДобавитьЗапись(тзМаршруты, "Склад4", "Склад3", 5);
ДобавитьЗапись(тзМаршруты, "Склад4", "Склад5", 6);
СкладОткуда = "Склад1";
СкладКуда = "Склад5";

тзПути = КратчайшийПутьПоФлойду(СкладОткуда, СкладКуда, тзМаршруты);
Если тзПути<>Неопределено Тогда
  Сообщить("Минимальный путь: "+тзПути.Итог("Расстояние"));
  Сообщить("Найденные маршруты:");
  Для Каждого ТекМаршрут Из  тзПути Цикл
    Сообщить(""+ТекМаршрут .СкладОткуда+" - "+ТекМаршрут.СкладКуда+"-"+ТекМаршрут.Расстояние);
  КонецЦикла;
КонецЕсли;

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

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1753    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4415    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7458    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7854    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4444    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8834    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7801    dusha0020    8    

70
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. dablack 09.01.16 12:49 Сейчас в теме
Таблицу в которой около 40 "складов" (не строк) обработает ? пробовали ?
2. Garykom 16 09.01.16 14:22 Сейчас в теме
(1) dablack,
нет не пробовал, скиньте пример такой таблицы, попробую и выложу результат
но до 1000 складов нормально должно работать
3. dablack 10.01.16 17:08 Сейчас в теме
Вот файл таблицы значений через ЗначениеВФайл. Таблица из 32 пунктов.
Попробуйте пожалуйста.
Прикрепленные файлы:
dist.tz
4. Garykom 16 11.01.16 13:56 Сейчас в теме
(3) dablack, все пути из Склад1 в (Склад2 - Склад32) в один шаг самые короткие

P.S. хотя ошибаюсь, сразу не заметил что вместо прямого Склад1 - Склад20 = 310 395

Начали расчет: 11.01.2016 13:51:46 Склад1 - Склад20
Окончили расчет: 11.01.2016 13:51:47 Склад1 - Склад20
Минимальный путь: 310 394
|СкладОткуда|СкладКуда|Расстояние
|Склад1|Склад27|243 052
|Склад27|Склад20|67 342

на 1 меньше ))
Прикрепленные файлы:
32 склада.txt
5. Garykom 16 03.02.16 20:07 Сейчас в теме
Кому интересно есть продвинутая версия.
Которая умеет считать маршруты когда они не постоянные статичные.
А разные (периодические) по разным по дням недели.
6. ildarovich 7850 04.02.16 13:37 Сейчас в теме
Попытался сравнить быстродействие приведенного здесь метода с методом из статьи Определение кратчайших путей, критических путей одним запросом. . По идее, алгоритм Флойда должен иметь сравнимое быстродействие. Его оценка трудоемкости ~O(N^3), метода "матричного умножения" ~O(Log(K)*N^3), где К - диаметр графа. Множитель Log(K) нивелируется тем, что массовые вычисления в запросе делаются "пакетом" и поэтому быстрее в 10-50 раз.
Однако столкнулся с тем, что на схеме метро функция не работает. Насколько я понял, отрезки пути, найденные алгоритмом, не находятся в исходном графе.
Прилагаю файл связности станций питерского метро, полученный сохранением в текстовом файле строки, равной ЗначениеВСтрокуВнутр(ТаблицаМаршрутов).
Прикрепленные файлы:
МетроПитер.txt
7. Garykom 16 08.02.16 11:20 Сейчас в теме
(6) ildarovich, боюсь некорректно сравнивать эти два метода.
Флойд долго думает, но считает сразу одновременно все длины и находит кратчайшие пути между всеми парами вершин.
Т.е. после расчета и сохранения в массивы результат выдается мгновенно для любой пары вершин.
8. ildarovich 7850 08.02.16 12:13 Сейчас в теме
(7) думаю, вы невнимательно прочитали статью, на которую я неоднократно ссылался. Это метод, решающий ту же задачу "All Pairs Shortest Paths (APSP) problem". Так же находятся кратчайшие расстояния между всеми парами вершин. Поэтому сравнивать эти решения можно и нужно.

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

Кстати, проблема восстановления кратчайшего пути по кратчайшим расстояниям между всеми парами в статье решается гораздо проще. В кратчайший путь включаются все вершины ПунктПути, обладающие свойством:
КратчайшееРасстояние(Откуда, ПунктПути) + КратчайшееРасстояние(ПунктПути, Куда) = КратчайшееРасстояние(Откуда, Куда)
Пункты упорядочиваются по КратчайшееРасстояние(Откуда, ПунктПути). При этом никаких предыдущих вершин вычислять и хранить вообще не нужно. Дополнительно это дает возможность вывода нескольких равнозначных вариантов равной длины. Затраты на проверку лишних вершин, которые потом не войдут путь, очень малы (по отношению к основным затратам метода).
9. ildarovich 7850 08.02.16 16:15 Сейчас в теме
+(6) файлы схемы метро в другом формате (mxl, xls)
Прикрепленные файлы:
МетроПитер.mxl
МетроПитер.xls
МетроМосква.mxl
10. Garykom 16 08.02.16 16:25 Сейчас в теме
(9) ildarovich, все работает

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

Считал 15 минут потому что 140 станций * 7 дней вершин
Прикрепленные файлы:
11. ildarovich 7850 08.02.16 18:25 Сейчас в теме
(10) я взял функцию из вашей обработки, вставил в свою, получил ошибку (см.скриншоты). - Что я делаю не так?

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

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

Про
потому что 140 станций * 7 дней вершин
не понял. В Питере ~65 станций. 140 - это число связей между станциями.

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

насчет ошибки все правильно, восстановление пути для Флойда возможно двумя способами :) http://hci.fenster.name/304y/lab5/
в выложенном сделан "...В этом случае значение массива C[j][k] после окончания алгоритма будет указывать одну из вершин, через которую проходит путь от j к k ..."
выложенный алгоритм правильно считает кратчайший путь, но не всегда может его восстановить
13. ildarovich 7850 09.02.16 21:40 Сейчас в теме
(12) в общем, пришлось свою реализацию сделать. Вот что получилось у меня:
Функция КратчайшийПутьФлойд(Откуда, Куда, Дуги) Экспорт
	// загрузка графа в "соответствие соответствий" так, что Пути[Откуда][Куда] = Длина
	Пути = Новый Соответствие;
	Для каждого Дуга Из Дуги Цикл
		Пути[Дуга.Откуда] = ?(Пути[Дуга.Откуда] = Неопределено, Новый Соответствие, Пути[Дуга.Откуда]);
		Пути[Дуга.Откуда][Дуга.Куда] = Дуга.Длина
	КонецЦикла;
	// три вложенных цикла по узлам графа
	Для каждого Узел1 Из Пути Цикл // тогда Узел.Ключ - это одна вершина из полного множества вершин  
		Для каждого Узел2 Из Пути Цикл 
			Если Пути[Узел2.Ключ][Узел1.Ключ] <> Неопределено Тогда
				Для каждого Узел3 Из Узел1.Значение Цикл // здесь только вершины, связанные с Узел1.Ключ 
					Длина = Пути[Узел2.Ключ][Узел3.Ключ];
					Обход = Пути[Узел2.Ключ][Узел1.Ключ] + Узел3.Значение; // Узел3.Значение == Пути[Узел1.Ключ][Узел3.Ключ]
					Пути[Узел2.Ключ][Узел3.Ключ] = ?(Длина = Неопределено, Обход, Мин(Длина, Обход))
				КонецЦикла 
			КонецЕсли 
		КонецЦикла 
	КонецЦикла;
	// восстановление пути
	Путь = Дуги.СкопироватьКолонки("Куда, Длина");
	Путь.Добавить().Куда = Откуда;
	Путь.Добавить().Куда = Куда;
	Путь[1].Длина = Пути[Откуда][Куда];
	Для каждого Узел Из Пути Цикл 
		Если Пути[Откуда][Узел.Ключ] <> Неопределено И Пути[Узел.Ключ][Куда] <> Неопределено 
			И Пути[Откуда][Узел.Ключ] + Пути[Узел.Ключ][Куда] = Пути[Откуда][Куда] Тогда
			ЗаполнитьЗначенияСвойств(Путь.Добавить(), Новый Структура("Куда, Длина", Узел.Ключ, Пути[Откуда][Узел.Ключ]))
		КонецЕсли
	КонецЦикла;
	Путь.Сортировать("Длина");
	Возврат Путь
КонецФункции // КратчайшийПуть()
Показать
На примере московского метро примерно на 30% быстрее запроса получается.
По ходу дела нашел на ИС статью на смежную тему: Реализация алгоритма Дейкстры. В статье также заявлена и реализация Флойда.

... Ну и еще. Поскольку массив работает быстрее соответствия, попробовал, как и автор, на всякий случай вариант с массивом:
Функция КратчайшийПуть(Откуда, Куда, Дуги) Экспорт
	// нумерация вершин
	Номер = Новый Соответствие;
	Номер[Откуда] = 0;
	Номер[Куда  ] = 1; // Если Откуда = Куда Тогда Возврат Новый ТаблицаЗначений КонецЕсли; 
	Для каждого Дуга Из Дуги Цикл
		Номер[Дуга.Откуда] = ?(Номер[Дуга.Откуда] = Неопределено, Номер.Количество(), Номер[Дуга.Откуда]);
		Номер[Дуга.Куда  ] = ?(Номер[Дуга.Куда  ] = Неопределено, Номер.Количество(), Номер[Дуга.Куда  ])
	КонецЦикла;                                                                      
	// инициализация массива-матрицы инцидентности
	ВГраница = Номер.Количество() - 1;
	Пути = Новый Массив(ВГраница + 1, ВГраница + 1);
	Много = 999999999;
	Для ё = 0 По ВГраница Цикл
		Для ж = 0 По ВГраница Цикл
			Пути[ё][ж] = ?(ё = ж, 0, Много) 
		КонецЦикла 
	КонецЦикла; 
	// загрузка графа в массив
	Для каждого Дуга Из Дуги Цикл
		Пути[Номер[Дуга.Откуда]][Номер[Дуга.Куда]] = Дуга.Длина
	КонецЦикла;
	// тело алгоритма Флойда-Уоршолла
	Для к = 0 По ВГраница Цикл
		Для ё = 0 По ВГраница Цикл
			Для ж = 0 По ВГраница Цикл
				Пути[ё][ж] = Мин(Пути[ё][ж], Пути[ё][к] + Пути[к][ж]) 
			КонецЦикла                                                                       
		КонецЦикла 
	КонецЦикла;
	// восстановление пути
	Путь = Дуги.СкопироватьКолонки("Куда, Длина");
	Для каждого Элемент Из Номер Цикл 
		Если Пути[0][Элемент.Значение] + Пути[Элемент.Значение][1] = Пути[0][1] Тогда
			ЗаполнитьЗначенияСвойств(Путь.Добавить(), Новый Структура("Куда, Длина", Элемент.Ключ, Пути[0][Элемент.Значение]))
		КонецЕсли
	КонецЦикла;
	Путь.Сортировать("Длина");
	Возврат Путь
КонецФункции // КратчайшийПуть()                                                           
Показать
Но получилось медленнее (в два раза к запросу)! Наверное, из-за экономия на переборе во вложенном цикле, где при использовании соответствия учитываются только существующие на данной итерации связи. В итоге для большой реальной задачи все же рекомендую использовать вариант с соответствием. Он на данный момент самый быстрый, да и кода там меньше.
14. Garykom 16 11.02.16 13:31 Сейчас в теме
(13) ildarovich, на 30% быстрее получилось потому что соединили алгоритмы Флойда и Дейкстры.
И еще потому что вершин и ребер мало. Особенно потому что количество ребер практически равно количеству вершин - линии метро однако.

Попробуйте на 500 вершинах и 5000 ребер? Запрос в этом случае умрет, вариант с соответствием будем в 2-2.5 раза медленнее чем с массивами. Точно будет зависеть от отношения количества вершин к количеству ребер.
15. ildarovich 7850 11.02.16 14:39 Сейчас в теме
(14)
Запрос в этом случае умрет, вариант с соответствием будем в 2-2.5 раза медленнее чем с массивами
- А ставку сделать готовы?
соединили алгоритмы Флойда и Дейкстры
Это не так. В алгоритме Дейкстры требуется минимум в неразвитых ветвях искать. Здесь поиска минимума и развития ветвей нет.
16. Garykom 16 12.02.16 10:40 Сейчас в теме
(15) ildarovich,
- А ставку сделать готовы?

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

Это не так. В алгоритме Дейкстры требуется минимум в неразвитых ветвях искать. Здесь поиска минимума и развития ветвей нет.

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

Модернизированный Флойд:
"Но существует решение и за \sum_{n,\;n,\;n}O(1) = O(n^2), где хранятся значения не для всех вершин, а только значения для предыдущей вершины, так как следующая получается рекурсивно."
https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D­0%A4%D0%BB%D0%BE%D0%B9%D0%B4%D0%B0_%E2%80%94_%D0%A3%D0%BE%D1­%80%D1%88%D0%B5%D0%BB%D0%BB%D0%B0

И да через битовые маски еще быстрее...
17. ildarovich 7850 12.02.16 14:02 Сейчас в теме
(16)
- А ставку сделать готовы?
Я написал это, чтобы побудить вас поспорить на что-нибудь, чтобы мне было интереснее сравнительное тестирование провести. Задача я бы не сказал, чтобы популярная, поэтому пока не решил, стоит ли этим заниматься.
Статью в Википедии я и раньше видел, этот оборот (про N^2) не понял, честно говоря (источник там не указан). В английской версии этой фразы нет. Если вы поняли о чем там речь или знаете где можно про прочитать, подскажите.
Так что битовые маски не ЕЩЕ быстрее, а просто быстрее. Ну а так как битовых масок в 1С нет, то соответствие а последнем цикле и играет роль маски - позволяет не проверять не существующие дуги.
18. Garykom 16 12.02.16 17:46 Сейчас в теме
(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С, когда запускают тестирование из "конфигуратора через отладку", и напрямую запускают "режим предприятия"
в этом случае отладчик слегка портит результаты
Оставьте свое сообщение