Поиск минимального пути в графе

[Sicker]

Хочу представить вам свой метод поиска минимального пути в графе Он может использоваться как для неориентированного графа с положительными ребрами, так и для ориентированного с отрицательными ребрами (для нахождения минимального пути в таком графе не должно быть отрицательных циклов, алгоритм это определяет).
Собственно, начинаем мы с исходной вершины, которая имеет статус активной (вершины могут быть активными и неактивными), каждая вершина (будь она активна или неактивна) характеризуется следующими параметрами:
1. Активностью, т.е. для этой вершины проделываем определенный алгоритм, после чего она становится неактивной до определенного времени (которое может и не наступить)
2. Временем достижения (длиной маршрута от начальной точки), оно может меняться в процессе работы алгоритма, пока не придет к минимальному
3. Ребром прихода, по которому пришел сигнал от другой активной вершины.
Собственно, на каждом этапе мы имеем определенное количество активных вершин, для каждой активной вершины проделываем следующий алгоритм
Делаем ее неактивной и посылаем сигналы ко всем ребрам этой вершины, кроме ребра прихода, и для каждой достигнутой таким способом вершины производим операцию:
Если принесенное нами время (которое равно времени достижения нашей предыдущей вершины плюс вес ребра) меньше, чем время достижения вершины, которой мы сейчас достигли, то мы выставляем в этой вершине наше новое время, новое ребро прихода (откуда мы пришли) и делаем ее активной. Если нет, то ничего не меняем. (по умолчанию у всех вершин нулевое время достижения, и нет ребра прихода)
Продолжаем работу нашего алгоритма до тех пор, пока не останется ни одной активной вершины.
После работы нашего алгоритма у каждой вершины будет свое минимальное время прихода (минимальная длина маршрута) от начальной точки. Мы также можем восстановить минимальную траекторию до начальной точки, просто двигаясь по ребрам прихода.
Если в графе есть отрицательный цикл, то алгоритм будет работать бесконечно долго, в таком случае условием его остановки будет момент, когда одно из времен достижения станет меньше суммы всех отрицательным ребер в графе.
Сложность такого алгоритма полиномиальная - $O(n)$ без отрицательных ребер, а с отрицательными может быть $O(n^2)$
Что скажете?

[mihaild]

Sicker в сообщении #1476781 писал(а):

по умолчанию у всех вершин нулевое время достижения

Тяжко будет получить меньшее нуля время прихода. Может по умолчанию время всё-таки бесконечное (дальше исхожу из этого)?

Sicker в сообщении #1476781 писал(а):

Что скажете?

Скажу что сложность нужно доказывать (у вас же вершины туда-сюда могут переключаться). И вроде бы она побольше получается.

[Sicker]

mihaild в сообщении #1476789 писал(а):

Тяжко будет получить меньшее нуля время прихода.

Точнее, большее нуля

mihaild в сообщении #1476789 писал(а):

Может по умолчанию время всё-таки бесконечное (дальше исхожу из этого)?

Да, точно

mihaild в сообщении #1476789 писал(а):

Скажу что сложность нужно доказывать (у вас же вершины туда-сюда могут переключаться). И вроде бы она побольше получается.

Интересно было бы посчитать.
А сам алгоритм вроде корректный? Он является модификацией волнового алгоритма

[kotenok gav]

А у этого алгоритма есть особые отличия от алгоритма Дейкстры?

[Sicker]

kotenok gav в сообщении #1476794 писал(а):

А у этого алгоритма есть особые отличия от алгоритма Дейкстры?

Да, он может работать с отрицательными ребрами

[kotenok gav]

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

[Sicker]

kotenok gav
Не получиться так, у вас для путей с разным числом ребер не одинаково изменятся значения

[kotenok gav]

Хм, да. Ну тогда просто увеличиваем ребра на одно число, путь от этого не изменится.

[Sicker]

kotenok gav в сообщении #1476800 писал(а):

Хм, да. Ну тогда просто увеличиваем ребра на одно число, путь от этого не изменится.

Опять же

Sicker в сообщении #1476798 писал(а):

у вас для путей с разным числом ребер не одинаково изменятся значения

у вас изменится сам путь

[kotenok gav]

Ок. Если не ошибаюсь, ваш алгоритм - алгоритм Беллмана — Форда.

[Sicker]

kotenok gav
А вы точно уверены?

[kotenok gav]

Почти уверен, но гарантировать не могу. Откройте сами статью в Википедии и почитайте.

[B@R5uk]

Sicker в сообщении #1476781 писал(а):

по умолчанию у всех вершин нулевое время достижения, и нет ребра прихода

Что-то в этой инициализации не то. Поскольку

Sicker в сообщении #1476781 писал(а):

Если принесенное нами время ... меньше, чем время достижения вершины ..., то мы выставляем в этой вершине наше новое время, новое ребро прихода ... и делаем ее активной.

Все принесённые положительные времена будут выкидываться, поскольку у вершины уже есть нулевое время, а любое положительное будет больше. Соответственно, ни одно ребро прихода с положительным путём не будет установлено.

Sicker в сообщении #1476781 писал(а):

Что скажете?

Написали бы для начала программу и постестили бы её на каких-нибудь примерах, разобранных в википедии.

[Sicker]

B@R5uk
Читайте комментарии ниже

[Sender]

Думаю, для начала не помешало бы сколько-нибудь формально записать алгоритм, а то написанное можно интерпретировать по-разному. Например, что-то в этом духе(не уверен, что форум поддерживает).
https://www.math-linux.com/latex-26/faq/latex-faq/article/how-to-write-algorithm-and-pseudocode-in-latex-usepackage-algorithm-usepackage-algorithmic