gifts2017

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

Опубликовал Garykom (Garykom) в раздел Программирование - Практика программирования

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

Алгоритм Флойда — Уоршелла — динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Разработан в 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";

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

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

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

См. также

Подписаться Добавить вознаграждение

Комментарии

1. Sergey Mosalov (dablack) 09.01.16 12:49
Таблицу в которой около 40 "складов" (не строк) обработает ? пробовали ?
2. Garykom (Garykom) 09.01.16 14:22
(1) dablack,
нет не пробовал, скиньте пример такой таблицы, попробую и выложу результат
но до 1000 складов нормально должно работать
3. Sergey Mosalov (dablack) 10.01.16 17:08
Вот файл таблицы значений через ЗначениеВФайл. Таблица из 32 пунктов.
Попробуйте пожалуйста.
Прикрепленные файлы:
dist.tz
4. Garykom (Garykom) 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 (Garykom) 03.02.16 20:07
Кому интересно есть продвинутая версия.
Которая умеет считать маршруты когда они не постоянные статичные.
А разные (периодические) по разным по дням недели.
6. Сергей (ildarovich) 04.02.16 13:37
Попытался сравнить быстродействие приведенного здесь метода с методом из статьи Определение кратчайших путей, критических путей одним запросом. . По идее, алгоритм Флойда должен иметь сравнимое быстродействие. Его оценка трудоемкости ~O(N^3), метода "матричного умножения" ~O(Log(K)*N^3), где К - диаметр графа. Множитель Log(K) нивелируется тем, что массовые вычисления в запросе делаются "пакетом" и поэтому быстрее в 10-50 раз.
Однако столкнулся с тем, что на схеме метро функция не работает. Насколько я понял, отрезки пути, найденные алгоритмом, не находятся в исходном графе.
Прилагаю файл связности станций питерского метро, полученный сохранением в текстовом файле строки, равной ЗначениеВСтрокуВнутр(ТаблицаМаршрутов).
Прикрепленные файлы:
МетроПитер.txt
7. Garykom (Garykom) 08.02.16 11:20
(6) ildarovich, боюсь некорректно сравнивать эти два метода.
Флойд долго думает, но считает сразу одновременно все длины и находит кратчайшие пути между всеми парами вершин.
Т.е. после расчета и сохранения в массивы результат выдается мгновенно для любой пары вершин.
8. Сергей (ildarovich) 08.02.16 12:13
(7) Garykom, думаю, вы невнимательно прочитали статью, на которую я неоднократно ссылался. Это метод, решающий ту же задачу "All Pairs Shortest Paths (APSP) problem". Так же находятся кратчайшие расстояния между всеми парами вершин. Поэтому сравнивать эти решения можно и нужно.

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

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

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

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

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

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

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

В общем, хотелось бы разобраться и получить результат сравнения по скорости, не отлаживая самому вашу разработку.
Прикрепленные файлы:
12. Garykom (Garykom) 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) 09.02.16 21:40
(12) Garykom, в общем, пришлось свою реализацию сделать. Вот что получилось у меня:
Функция КратчайшийПутьФлойд(Откуда, Куда, Дуги) Экспорт
	// загрузка графа в "соответствие соответствий" так, что Пути[Откуда][Куда] = Длина
	Пути = Новый Соответствие;
	Для каждого Дуга Из Дуги Цикл
		Пути[Дуга.Откуда] = ?(Пути[Дуга.Откуда] = Неопределено, Новый Соответствие, Пути[Дуга.Откуда]);
		Пути[Дуга.Откуда][Дуга.Куда] = Дуга.Длина
	КонецЦикла;
	// три вложенных цикла по узлам графа
	Для каждого Узел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 (Garykom) 11.02.16 13:31
(13) ildarovich, на 30% быстрее получилось потому что соединили алгоритмы Флойда и Дейкстры.
И еще потому что вершин и ребер мало. Особенно потому что количество ребер практически равно количеству вершин - линии метро однако.

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