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

09.01.16

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

+17 –
>
  • floyd_uorshell.jpg
  • Обработка.png
Поиск кратчайшего пути между точками (складами) по алгоритму Флойда-Уоршелла

Файлы

ВНИМАНИЕ: Файлы из Базы знаний - это исходный код разработки. Это примеры решения задач, шаблоны, заготовки, "строительные материалы" для учетной системы. Файлы ориентированы на специалистов 1С, которые могут разобраться в коде и оптимизировать программу для запуска в базе данных. Гарантии работоспособности нет. Возврата нет. Технической поддержки нет.

Наименование Скачано Купить файл
FindFloid
.epf 7,62Kb ver:1.0
28 2 500 руб. Купить

Подписка PRO — скачивайте любые файлы со скидкой до 85% из Базы знаний

Оформите подписку на компанию для решения рабочих задач

Оформить подписку и скачать решение со скидкой

Вы можете заказать платную доработку или адаптацию этой разработки под вашу конфигурацию на «Бирже заказов».

  • 0% комиссии — оплата напрямую исполнителю;
  • Исполнители любого масштаба — от отдельных специалистов до команд под проект;
  • Прямой обмен контактами между заказчиком и исполнителем;
  • Безопасная сделка — при необходимости;
  • Рейтинги, кейсы и прозрачная система откликов.

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

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

Вступайте в нашу телеграмм-группу Инфостарт

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

+17 –

См. также

Улучшенный алгоритм Левенштейна для 1С: интеллектуальное сравнение строк

Математика и алгоритмы Разработчик 1С 8.3 Абонемент ($m)

Данная внешняя обработка для платформы 1С:Предприятие реализует усовершенствованный алгоритм Левенштейна для вычисления схожести строк с учетом различных лингвистических особенностей русского языка. В отличие от классической реализации, этот алгоритм учитывает фонетические, визуальные и контекстные особенности набора текста.

1 стартмани

07.11.2025    7068    18    InFlach    17    

27
Поиск дублей по полям ключей шапки, табличных частей

Математика и алгоритмы Запросы Разработчик 1С:Предприятие 8 Бесплатно (free)

Рассмотрим быстрый алгоритм поиска дублей с использованием hash функции по набору полей шапки и табличных частей.

08.07.2024    9225    ivanov660    9    

24
Метод Дугласа-Пойкера

Математика и алгоритмы Разработчик 1С:Предприятие 8 1C:Бухгалтерия Россия Абонемент ($m)

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

1 стартмани

30.01.2024    17041    stopa85    12    

44
Алгоритм симплекс-метода

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

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

19.10.2023    25311    user1959478    57    

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

Математика и алгоритмы Разное 1С:Предприятие 8 1C:Бухгалтерия Россия Абонемент ($m)

Расширение (+ обработка) представляют собою математический тренажер. Ваш ребенок сможет проверить свои знание на математические вычисление до 100.

2 стартмани

29.09.2023    15773    maksa2005    8    

27
Регулярки на 1С

Математика и алгоритмы Инструментарий разработчика Разработчик 1С:Предприятие 8 Россия Абонемент ($m)

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

1 стартмани

09.06.2023    25659    13    SpaceOfMyHead    20    

65
Мини-обзор разных решений задач

Математика и алгоритмы Разработчик 1С:Предприятие 8 Бесплатно (free)

Три задачи - три идеи - три решения. Мало кода, много смысла. Мини-статья.

03.04.2023    17766    RustIG    10    

30
Тестирование средств 1С для решения СЛАУ

Механизмы платформы 1С Математика и алгоритмы Разработчик 1С:Предприятие 8 Россия Бесплатно (free)

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

23.11.2022    16661    gzharkoj    17    

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

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

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

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

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

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

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

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

В общем, хотелось бы разобраться и получить результат сравнения по скорости, не отлаживая самому вашу разработку.
Прикрепленные файлы:
+ – Ответить
12. Garykom 17 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 8066 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 17 11.02.16 13:31 Сейчас в теме
(13) ildarovich, на 30% быстрее получилось потому что соединили алгоритмы Флойда и Дейкстры.
И еще потому что вершин и ребер мало. Особенно потому что количество ребер практически равно количеству вершин - линии метро однако.

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