Рассмотрен алгоритмический подход к решению задачи поиска кратчайшего пути и разработана его реализация, которая позволяет использовать процедуру наиболее эффективно
перевозки, алгоритм Флойда, задача выбора кратчайшего пути
В настоящее время не существует «наилучшего» алгоритма для всех видов транспортных задач, а исследования в этой области направлены на разработку и реализацию «специальных» процедур поиска кратчайшего пути, которые способны учитывать особенности методов [1, 2].
Рассмотрим подробнее алгоритм Флойда. В нем сеть представлена в виде квадратной матрицы с n строками и n столбцами. Элемент (i, j) равен расстоянию dij от узла i к узлу j, которое имеет конечное значение, если существует дуга (i, j), и равен бесконечности в противном случае. Основная идея метода Флойда сводится к тому, что есть три узла i, j и k и заданы расстояния между ними. Если выполняется неравенство dij + dkj < dik, то целесообразно заменить путь i → k путем i → j → k. Такая замена (далее ее будем условно называть треугольным оператором) выполняется систематически в процессе выполнения алгоритма Флойда.
Описание основного алгоритмического подхода для задач поиска кратчайших путей приведено на рисунке 1.
Исследование будет сосредоточено на создании «специального» алгоритма, произведённого на основных алгоритмических парадигмах, зависящих от структуры данных и порядка выбора узлов, что может существенно повлиять на его производительность.
Рисунок 1 – Фрагмент алгоритма решения задачи методом Флойда
Проведенные исследования позволяют заключить, что метод Флойда возможно использовать при матричном решении транспортных задач для создания эффективных и специализированных алгоритмов поиска кратчайшего пути, впоследствии это позволит стимулировать развитие и других «специальных» процедур в области транспорта.
1. Асламова В.С. Алгоритмы решения транспортных, сетевых задач и за-дач о назначении. Часть вторая. Учебное пособие. / В.С. Асламова, И.М. Кулако-ва, М.Н. Крипак.- Ангарск: АГТА, 2009. - 190 с.
2. Крипак М.Н. Автоматизация алгоритма Литтла для решения задачи ком-мивояжера / Крипак М.Н., Кулакова И.М., Лебедева О.А. Современные техноло-гии. Системный анализ. Моделирование. 2015. № 4 (48). С. 160-163.
