Временная сложность алгоритма Дейкстры при использовании матрицы смежности и связного списка смежности

Question

Для графа с v вершинами и e ребрами и полосой, хранящейся в двоичной минимальной куче, время выполнения в худшем случае составляет O((n+e)lg(n)).Однако это предполагает, что мы используем связанный список смежности для представления графа.При использовании матрицы смежности для прохождения требуется O(n^2), в то время как представление связанного списка можно просмотреть в O(n+e).

Следовательно, из-за использования матрицы для представления графика время выполнения Дейкстры изменится на O(n^2lg(n))?

Answer 1

Стоимость O (log n) оплачивается для обработки ребер, а не для обхода графа, поэтому, если вы знаете фактическое число ребер в графе, тогда алгоритм Дейкстры на матрице смежности с min-куча находится в пределах O (n ^ 2 + (n + e) ​​log (n)) время.