An algorithmic approach to solving the problem of finding the shortest path is considered and implementation methods are developed that allow using the procedure most efficiently
transportation, Floyd's algorithm, shortest path selection problem
В настоящее время не существует «наилучшего» алгоритма для всех видов транспортных задач, а исследования в этой области направлены на разработку и реализацию «специальных» процедур поиска кратчайшего пути, которые способны учитывать особенности методов [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. Aslamova V.S. Algoritmy resheniya transportnyh, setevyh zadach i za-dach o naznachenii. Chast' vtoraya. Uchebnoe posobie. / V.S. Aslamova, I.M. Kulako-va, M.N. Kripak.- Angarsk: AGTA, 2009. - 190 s.
2. Kripak M.N. Avtomatizaciya algoritma Littla dlya resheniya zadachi kom-mivoyazhera / Kripak M.N., Kulakova I.M., Lebedeva O.A. Sovremennye tehnolo-gii. Sistemnyy analiz. Modelirovanie. 2015. № 4 (48). S. 160-163.
