В этой статье, насколько я понимаю, просто распараллелили известный алгоритм. Меня немного удивляет, что про это пишут статью, а не документацию к софту, но, возможно, в этой области так принято.
И кстати, символ
например:
входит в систему классического формализма?
А в каком контексте?
В псевдокоде - да, скорее всего всем будет понятно.
Он в лекциях обозначен, как (greedy). Если я не ошибаюсь, этот термин означает, что алгоритм неточный
Нет, это значит что он жадный, т.е. начинает рассмотрение вариантов с максимального по какому-то параметру. В зависимости от задачи, полученное решение может быть как точным, так и приближенным. Алгоритм Дейкстры (для случая неотрицательных весов) даёт точный результат.
Кроме того, смущает сложность алгоритма
.
В зависимости от того, как реализовывать алгоритм Дейкстры, у него получается разная сложность - если использовать кучу, то будет
, если использовать Фибоначчиеву кучу - то
. Есть всякие совсем хитрые реализации, например за
, но я не знаю, как они устроены.
Известен и алгоритм, работающий за
(Thorup, "Undirected Single Source Shortest Paths in Linear Time"), причем сравнительно новый - 1999 года. Но на практике он сильно сложнее и не сильно быстрее алгоритма Дейкстры.
Мой, например,
.
Вы учитываете, что в графе рёбер может быть сильно больше, чем
, и нам как минимум их веса прочитать надо?
Ну и отсутствие понятия связанности по ребрам и множдесва окрестности вершины
Не очень понял - это Вы про то, что в Вашем алгоритме эти понятия не нужны, или что в описании алгоритма Дейкстры они используются, но не определяются?