Сравнение среднего и наихудшего времени работы алгоритма Левита с другими алгоритмами нахождения кратчайших путей

1.2 Рассмотрение области применения рассматриваемых алгоритмов и оценки предполагаемого времени их работы.
Алгоритмы Дейкстры и Форда-Беллмана давно известны и изучены, поэтому мы берем их для сравнения с малоизученным алгоритмом Левита.
Алгоритм Дейкстры применяется только для графов с положительными весами ребер. Существует 2 варианта алгоритма Дейкстры. Первый вариант применятся для разряженных графов, в которых количество ребер не велико по сравнению с количеством вершин. Его асимптотика времени работы равна О(m log n). Второй вариант применяется для графов близких к полным, с большим количеством ребер. Его асимптотика времени работы равна О(n2+m). Если количество ребер m примерно равно n2 (полный граф), то для первого варианта алгоритма получается время работы О(n2 log n), для второго – О(n2). Если количество ребер m примерно равно n (дерево), то для первого варианта алгоритма получается время работы О(n log n), для второго – О(n2).
Алгоритм Белмана-Форда допускает вычисления на графах с отрицательным весом ребер. Асимптотика времени работы равна O(nm). Если количество ребер m примерно равно n2 (полный граф), то получается время работы О(n3). Если количество ребер m примерно равно n (дерево), то алгоритма получается время работы – О(n2). Время работы хуже, чем у алгоритма Дейкстры.
Оценка скорости алгоритма через O (О большое) показывает, с какой скоростью растет время работы в зависимости от числа операций, которое обозначается буквой – n, константы не учитываются, так как они не влияют на скорость роста времени. Это верхняя оценка, то есть количество операций и время работы растет не быстрее, чем выражение, заключенное в скобки.

В современном мире графы применяются во многих областях и позволяют решать широкий круг задач. Исследователь должен знать проблемы алгоритмов работы с графами, время их выполнения, возможные ошибки и соответствие типов графов тому или иному алгоритму.
Теория графов из академической дисциплины все более превращается в средство, владение которым становится решающим для успешного применения компьютеров во многих прикладных областях
Современные системы GPS навигации - наглядный пример использования графов сложной структуры и алгоритмов поиска кратчайших путей. Пункты назначения, улицы и целые города в навигаторе представляются в виде графов с огромным количеством вершин и ребер. Пользователь при выборе навигатора, в первую очередь обращает внимание на скорость его работы, которая напрямую зависит от скорости работы алгоритмов поиска кратчайших путей в графах.
Также теория графов применяется в задачах железнодорожных перевозок, авиаперелетов, при моделировании линий электропередач, различных инженерных сетей.
Решение транспортных задач требует максимальной скорости, следовательно, должны быть быстрыми и методы работы с графами.
Также задачи такого рода решаются на олимпиадах по программированию, и от участника требуется написать максимально эффективное решение. И с другой стороны жюри соревнований должны разрабатывать графы, на которых неэффективные алгоритмы, примененные участниками, не уложатся в отведенное время.
В данной работе выполняется исследование алгоритма Левита, который реализуется достаточно просто, то есть он может быть использован для различных встраиваемых систем, например GPS-навигаторов, но характеристики его работы мало исследованы.