‍Похоже, я придумал свой алгоритм поиска кратчайшего пути

Я реализовал, похоже, собственный алгоритм поиска кратчайшего пути с отрицательными ребрами графа.

Почему собственный? Я искал подобное решение, но не нашел, возможно, оно уже было реализовано, просто плохо поискал. Жду Нобелевскую премию =)

Додумался я до него путем модификации классического Дейкстры. Прошу адекватно отнестись к содержимому, ибо это моя первая статья, и, возможно, я ничего не придумывал и, вообще, этот алгоритм не работает вовсе (но по многочисленным тестам он работает правильно).

Повторюсь, алгоритм работает с отрицательными ребрами графа (но не с циклическими отрицательными). Чем этот алгоритм отличается от известного Беллмана-Форда?

Эвристической сложностью! У известного алгоритма сложность составляет O(En), где n - количество узлов, Е - количество ребер. У "моего" алгоритма такая же ассимптотическая сложность. Но по моим расчетам худшая сложность в большинстве случаев не достигается. А у Беллмана-Форда худших случаев намного больше (об этом далее). Более того, в среднем алгоритм не превышает оригинальной сложности алгоритма Дейкстры, а именно O(n2+E). Об этом тоже напишу далее. Реализация на языке Python:

P.S.
В статье исправлены многие моменты, спасибо сообществу за тест-кейсы и подсказки. Некоторые комментарии не будут актуальными (в том числе саркастически-оскорбительные), т.к. я считаю, что доказал работоспособность алгоритма.

https://habr.com/ru/articles/811051/


#python@bookflow

👉 @Bookflow