Сложность времени Дейкстры с использованием двоичной кучи

Question

Пусть G (V, E) - неориентированный граф с положительными весами ребер.Алгоритм кратчайшего пути Дейкстры с одним источником может быть реализован с использованием структуры данных двоичной кучи с временной сложностью:

1. O (| V | 2)
2. O (| E | + | V |log | V |)
3. O (| V | log | V |)
4. O ((| E | + | V |) log | V |)

========================================================================

Правильный ответ -

O ((| E | + | V |) log | V |)

========================================================================

Мой подход заключается в следующем -

O (V + V + VlogV + ElogV) = O (ElogV)

• O (V)инициализировать.
• O (V) для построения кучи.
• VlogV для выполнения Extract_Min
• ElogV для выполнения Decrease Key

Теперь, когда я получаю O (ElogV) и когда вижу варианты, часть меня говорит, что правильным является O (VlogV), потому что для разреженного Graph | V |= | E |, но, как я уже сказал, правильный ответ O ((| E | + | V |) log | V |).Итак, где я иду не так?

Answer 1

Позвольте мне сказать это так. Правильный ответ O ((E + V) logV)). Если у графа есть исходная вершина, недоступная для всех других вершин, VlogV может быть больше, чем ElogV. Но еслимы предполагаем, что исходная вершина достижима для каждой другой вершины, граф будет иметь по крайней мере V-1 ребер. Так что это будет ElogV. Это больше связано с достижимостью из исходной вершины.

Answer 2

Ну, вы правы, что сложность на самом деле O (E log V) .

Так как E может быть до (V ^2 - V) / 2 , это не то же самое, что O (V log V) .

Если у каждой вершины есть ребро, то V <= 2E</strong>, поэтому в этом случае O (E log V) = O ((E + V) log V) .Это обычный случай, и он соответствует «правильному» ответу.

Но технически, O (E log V) не совпадает с O ((E + V)) log V) , потому что в V может быть целый ряд разрозненных вершин.Однако в таком случае алгоритм Дейкстры никогда не увидит все эти вершины, поскольку он находит только вершины, связанные с одним источником.Поэтому, когда разница между этими двумя сложностями важна, вы правы, а «правильный ответ» - нет.