2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Поиск минимального пути в графе
Сообщение01.08.2020, 06:25 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Поиск минимального пути в графе
Сообщение01.08.2020, 08:56 
Заслуженный участник
Аватара пользователя


16/07/14
4133
Москва
Sicker в сообщении #1476781 писал(а):
по умолчанию у всех вершин нулевое время достижения

Тяжко будет получить меньшее нуля время прихода. Может по умолчанию время всё-таки бесконечное (дальше исхожу из этого)?
Sicker в сообщении #1476781 писал(а):
Что скажете?
Скажу что сложность нужно доказывать (у вас же вершины туда-сюда могут переключаться). И вроде бы она побольше получается.

 Профиль  
                  
 
 Re: Поиск минимального пути в графе
Сообщение01.08.2020, 09:15 
Аватара пользователя


13/08/13
03/10/20
4141
mihaild в сообщении #1476789 писал(а):
Тяжко будет получить меньшее нуля время прихода.

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

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

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

 Профиль  
                  
 
 Re: Поиск минимального пути в графе
Сообщение01.08.2020, 09:58 


21/05/16
3366
Аделаида
А у этого алгоритма есть особые отличия от алгоритма Дейкстры?

 Профиль  
                  
 
 Re: Поиск минимального пути в графе
Сообщение01.08.2020, 09:59 
Аватара пользователя


13/08/13
03/10/20
4141
kotenok gav в сообщении #1476794 писал(а):
А у этого алгоритма есть особые отличия от алгоритма Дейкстры?

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

 Профиль  
                  
 
 Re: Поиск минимального пути в графе
Сообщение01.08.2020, 10:01 


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

 Профиль  
                  
 
 Re: Поиск минимального пути в графе
Сообщение01.08.2020, 10:07 
Аватара пользователя


13/08/13
03/10/20
4141
kotenok gav
Не получиться так, у вас для путей с разным числом ребер не одинаково изменятся значения

 Профиль  
                  
 
 Re: Поиск минимального пути в графе
Сообщение01.08.2020, 10:21 


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

 Профиль  
                  
 
 Re: Поиск минимального пути в графе
Сообщение01.08.2020, 10:40 
Аватара пользователя


13/08/13
03/10/20
4141
kotenok gav в сообщении #1476800 писал(а):
Хм, да. Ну тогда просто увеличиваем ребра на одно число, путь от этого не изменится.

Опять же
Sicker в сообщении #1476798 писал(а):
у вас для путей с разным числом ребер не одинаково изменятся значения

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

 Профиль  
                  
 
 Re: Поиск минимального пути в графе
Сообщение01.08.2020, 11:03 


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

 Профиль  
                  
 
 Re: Поиск минимального пути в графе
Сообщение01.08.2020, 11:13 
Аватара пользователя


13/08/13
03/10/20
4141
kotenok gav
А вы точно уверены? :roll:

 Профиль  
                  
 
 Re: Поиск минимального пути в графе
Сообщение01.08.2020, 15:17 


21/05/16
3366
Аделаида
Почти уверен, но гарантировать не могу. Откройте сами статью в Википедии и почитайте.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

Модераторы: Karan, maxal, Toucan, PAV, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group