Сложность алгоритма - раздел Охрана труда, Формальное определение Сложность Алгоритма Дейкстры Зависит От Способа Нахождения Вершины V, ...
Сложность алгоритма Дейкстры зависит от способа нахождения вершины v, а также способа хранения множества непосещенных вершин и способа обновления меток. Обозначим через n количество вершин, а через m — количество ребер в графе G.
В простейшем случае, когда для поиска вершины с минимальным d[v] просматривается все множество вершин, а для хранения величин d — массив, время работы алгоритма есть O(n2 + m). Основной цикл выполняется порядка n раз, в каждом из них на нахождение минимума тратится порядка n операций, плюс количество релаксаций (смен меток), которое не превосходит количества ребер в исходном графе.
Для разреженных графов (то есть таких, для которых m много меньше n²) непосещенные вершины можно хранить в двоичной куче, а в качестве ключа использовать значения d[i], тогда время извлечения вершины из станет logn, при том, что время модификации d[i] возрастет до logn. Так как цикл выполняется порядка n раз, а количество релаксаций не больше m, скорость работы такой реализации O(nlogn + mlogn)
Если для хранения непосещенных вершин использовать фибоначчиеву кучу, для которой удаление происходит в среднем за O(logn), а уменьшение значения в среднем за O(1), то время работы алгоритма составит O(nlogn + m). Однако, согласно сайту intuit.ru,[3]
Формальное определение... Дан взвешенный ориентированный граф G V E без петель и дуг отрицательного... Пример...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Сложность алгоритма
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Описание
В простейшей реализации для хранения чисел d[i] можно использовать массив чисел, а для хранения принадлежности элемента множеству U — массив булевых переменных.
В начале алго
Доказательство корректности
Пусть l(v) — длина кратчайшего пути из вершины a в вершину v. Докажем по индукции, что в момент посещения любой вершины z, d(z)=l(z). База. Первой посещается вершина a. В этот момент d(a)=l(a)=
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов