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

Данное решение иллюстрирует использование соответствия при решении задач на графах. Благодаря этому достигается существенный выигрыш по быстродействию. С другой стороны, и алгоритм Флойда и алгоритм матричного умножения относятся к классу задач "All Pairs Shortest Paths (APSP) problem", то есть для определения расстояния между парой вершин являются избыточными. В данной задаче (для заданной пары вершин) лучше использовать алгоритм Дейкстры.

Функция КратчайшийПутьФлойд(Откуда, Куда, Дуги) Экспорт
    // загрузка графа в "соответствие соответствий" так, что Пути[Откуда][Куда] = Длина
    Пути = Новый Соответствие;
    Для каждого Дуга Из Дуги Цикл
        Пути[Дуга.Откуда] = ?(Пути[Дуга.Откуда] = Неопределено, Новый Соответствие, Пути[Дуга.Откуда]);
        Пути[Дуга.Откуда][Дуга.Куда] = Дуга.Длина
    КонецЦикла;
    // три вложенных цикла по узлам графа
    Для каждого Узел1 Из Пути Цикл // тогда Узел.Ключ - это одна вершина из полного множества вершин  
        Для каждого Узел2 Из Пути Цикл 
            Если Пути[Узел2.Ключ][Узел1.Ключ] <> Неопределено Тогда
                Для каждого Узел3 Из Узел1.Значение Цикл // здесь только вершины, связанные с Узел1.Ключ 
                    Длина = Пути[Узел2.Ключ][Узел3.Ключ];
                    Обход = Пути[Узел2.Ключ][Узел1.Ключ] + Узел3.Значение; // Узел3.Значение == Пути[Узел1.Ключ][Узел3.Ключ]
                    Пути[Узел2.Ключ][Узел3.Ключ] = ?(Длина = Неопределено, Обход, Мин(Длина, Обход))
                КонецЦикла 
            КонецЕсли 
        КонецЦикла 
    КонецЦикла;
    // восстановление пути
    Путь = Дуги.СкопироватьКолонки("Куда, Длина");
    Путь.Добавить().Куда = Откуда;
    Путь.Добавить().Куда = Куда;
    Путь[1].Длина = Пути[Откуда][Куда];
    Для каждого Узел Из Пути Цикл 
        Если Пути[Откуда][Узел.Ключ] <> Неопределено И Пути[Узел.Ключ][Куда] <> Неопределено 
            И Пути[Откуда][Узел.Ключ] + Пути[Узел.Ключ][Куда] = Пути[Откуда][Куда] Тогда
            ЗаполнитьЗначенияСвойств(Путь.Добавить(), Новый Структура("Куда, Длина", Узел.Ключ, Пути[Откуда][Узел.Ключ]))
        КонецЕсли
    КонецЦикла;
    Путь.Сортировать("Длина");
    Возврат Путь
КонецФункции // КратчайшийПуть()

Функция КратчайшийПутьФлойд(Откуда, Куда, Дуги) Экспорт
    // загрузка графа в "соответствие соответствий" так, что Пути[Откуда][Куда] = Длина
    Пути = Новый Соответствие;
    Для каждого Дуга Из Дуги Цикл
        Пути[Дуга.Откуда] = ?(Пути[Дуга.Откуда] = Неопределено, Новый Соответствие, Пути[Дуга.Откуда]);
        Пути[Дуга.Откуда][Дуга.Куда] = Дуга.Длина
    КонецЦикла;
    // три вложенных цикла по узлам графа
    Для каждого Узел1 Из Пути Цикл // тогда Узел.Ключ - это одна вершина из полного множества вершин  
        Для каждого Узел2 Из Пути Цикл 
            Если Пути[Узел2.Ключ][Узел1.Ключ] <> Неопределено Тогда
                Для каждого Узел3 Из Узел1.Значение Цикл // здесь только вершины, связанные с Узел1.Ключ 
                    Длина = Пути[Узел2.Ключ][Узел3.Ключ];
                    Обход = Пути[Узел2.Ключ][Узел1.Ключ] + Узел3.Значение; // Узел3.Значение == Пути[Узел1.Ключ][Узел3.Ключ]
                    Пути[Узел2.Ключ][Узел3.Ключ] = ?(Длина = Неопределено, Обход, Мин(Длина, Обход))
                КонецЦикла 
            КонецЕсли 
        КонецЦикла 
    КонецЦикла;
    // восстановление пути
    Путь = Дуги.СкопироватьКолонки("Куда, Длина");
    Путь.Добавить().Куда = Откуда;
    Путь.Добавить().Куда = Куда;
    Путь[1].Длина = Пути[Откуда][Куда];
    Для каждого Узел Из Пути Цикл 
        Если Пути[Откуда][Узел.Ключ] <> Неопределено И Пути[Узел.Ключ][Куда] <> Неопределено 
            И Пути[Откуда][Узел.Ключ] + Пути[Узел.Ключ][Куда] = Пути[Откуда][Куда] Тогда
            ЗаполнитьЗначенияСвойств(Путь.Добавить(), Новый Структура("Куда, Длина", Узел.Ключ, Пути[Откуда][Узел.Ключ]))
        КонецЕсли
    КонецЦикла;
    Путь.Сортировать("Длина");
    Возврат Путь
КонецФункции // КратчайшийПуть()