2014 dxdy logo

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

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




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


13/08/13

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

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


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

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

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


13/08/13

4323
mihaild в сообщении #1476789 писал(а):
Тяжко будет получить меньшее нуля время прихода.

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

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

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

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


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

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


13/08/13

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

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

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


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

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


13/08/13

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

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


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

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


13/08/13

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

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

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

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


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

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


13/08/13

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

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


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

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


26/05/12
1534
приходит весна?
Sicker в сообщении #1476781 писал(а):
по умолчанию у всех вершин нулевое время достижения, и нет ребра прихода

Что-то в этой инициализации не то. Поскольку
Sicker в сообщении #1476781 писал(а):
Если принесенное нами время ... меньше, чем время достижения вершины ..., то мы выставляем в этой вершине наше новое время, новое ребро прихода ... и делаем ее активной.

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

Sicker в сообщении #1476781 писал(а):
Что скажете?

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

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


13/08/13

4323
B@R5uk
Читайте комментарии ниже :-)

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


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

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

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



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

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


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

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