Анализ алгоритма Дейкстры¶

Наконец, давайте посмотрим на время выполнения алгоритма Дейкстры. Для начал отметим, что создание очереди с приоритетом занимает \(O(V)\) времени, поскольку первоначально мы добавляем в неё каждую вершину из графа. После того, как очередь сформирована, запускается цикл while. Он вычисляется один раз для каждого узла, так как все они добавлены с самого начала, а после только удаляются. Внутри цикла каждый вызов delMin занимает \(O(\log V)\) времени. Вместе цикл и вызов delMin дают \(O(V \log(V))\). Цикл for вычисляется единожды для каждого ребра графа, а внутри него происходит вызов decreaseKey. Вместе на это уходит \(O(E\log(V))\) времени. Таким образом, общее время выполнения получается равным \(O((V+E) \log(V)).\)