У меня есть определенная проблема с пониманием сложности алгоритма Djisktra, и я надеюсь, что кто-то сможет меня исправить.
В качестве примера я взял полный граф с n вершинами.
Вы выбираете начальную вершину, скажем, a1, отмечаете ее, а затем вычисляете все веса n-1 на ребрах. На)
Вы выбираете самый маленький. Скажем, вершину a2 и отметим ее. На)
После этого вы вычисляете n-2 новых веса на ребрах и ищите следующую, еще не отмеченную вершину, чтобы добавить свой набор отмеченных вершин.
И так далее...
Алгоритм выполняется до тех пор, пока вы не отметите все вершины. Сложность: n-1 + n-2 + ... + n - (n - 1) = Binom (n, 2), который находится в O (n ^ 2), а не в O (n * ln (n)), что я хотеть.
Я много раз читал, что люди используют кучу для оптимизации, но до сих пор не понимаю, как избежать вычислений Binom (n, 2).
Я должен ошибаться в какой-то момент, но не вижу где.
