Несмотря на многочисленность работ, связанных с проблемой нахождения кратчайших путей (КП), внимание к разработке эффективных по быстродействию алгоритмов построения КП не уменьшается. Это, в первую очередь, объясняется тем, что в подавляющем большинстве случаев такие алгоритмы часто используются для решения отдельных подзадач во многих приложениях в различных областях естествознания, и время решения общей оптимизационной задачи в значительной степени определяется временем построения КП. Рассмотрены 3 группы однокритериальных алгоритмов: сетевые комбинаторные алгоритмы; алгебраические или матричные алгоритмы; алгоритмы, базирующиеся на методах решения задач линейного программирования (LP). Приведены обзор, анализ и классификация методов и алгоритмов построения кратчайших путей на сетях и графах между заданными подмножествами узлов сети (Single Source Shortest Path - SSSP) и между всеми парами узлов (Shortest Path Tree - SPT или All Pairs Shortest Paths - APSP). Приведены оценки временной сложности наилучших известных алгоритмов для решения задач SSSP и APSP комбинаторными, матричными и LP-методами для сетей с неотрицательными длинами дуг и сетей с отрицательными длинами дуг и циклами отрицательной длины. Отмечается, что для решения отдельных SSSP-задач существуют "почти оптимальные" алгоритмы в теории и на практике, в то же время для решения более широкого класса задач, включая и APSP-проблему, имеются предпосылки для улучшения уже существующих алгоритмов. За последние годы эволюция методов решения задачи нахождения КП была связана с разработкой и дальнейшим усовершенствованием эффективных структур абстрактных типов данных для представления объектов задачи и созданием параллельных алгоритмов для многопроцессорного решения задачи. Определены основные направления дальнейших исследований по разработке эффективных методов и алгоритмов решения задач нахождения кратчайших путей.

  Повний текст PDF - 693.607 Kb    Зміст випуску     Цитування публікації

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"