2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Алгоритм дейкстры
Сообщение20.01.2015, 03:18 


30/11/14
54
Почему нельзя применять на графах с ребрами отрицательный длины? Нигде не нашёл объяснению этому, только упоминание, что нельзя. Самому же не получилось придумать такой пример графа, где бы он работал некорректно, поэтому приведите, пожалуйста, пример или объясните почему нельзя

 Профиль  
                  
 
 Re: Алгоритм дейкстры
Сообщение20.01.2015, 03:33 
Заслуженный участник


20/07/09
4026
МФТИ ФУПМ
Ну попробуйте $V=\{S,A,B\}, E = \{(S,A,1), (S,B,2), (B,A,-2)\}$. Начинать из $S$.

 Профиль  
                  
 
 Re: Алгоритм дейкстры
Сообщение20.01.2015, 12:25 


30/11/14
54
И в чём некорректность? Наикратчайший путь к В через вершину А.

 Профиль  
                  
 
 Re: Алгоритм дейкстры
Сообщение20.01.2015, 12:41 
Заслуженный участник


20/07/09
4026
МФТИ ФУПМ
greg2 в сообщении #965428 писал(а):
Наикратчайший путь к В через вершину А.
К $B$ нельзя через $A$ пробраться, нет ребра $(A,B)$. Можно наоборот.

 Профиль  
                  
 
 Re: Алгоритм дейкстры
Сообщение20.01.2015, 12:42 


30/11/14
54
А, я думла это неориентированный граф. Ну допустим, пробрались к А через B, путь равен нулю. В чем здесь проблема?

 Профиль  
                  
 
 Re: Алгоритм дейкстры
Сообщение20.01.2015, 12:45 
Заслуженный участник


20/07/09
4026
МФТИ ФУПМ
greg2 в сообщении #965439 писал(а):
Ну допустим, пробрались к А через B, путь равен нулю. В чем здесь проблема?
В том, что Дейкстра не сможет этот путь найти.

 Профиль  
                  
 
 Re: Алгоритм дейкстры
Сообщение20.01.2015, 12:51 


30/11/14
54
Именно вот это меня интересует. Дейскстра действует так:
1) смотрим все вершины, соседствующие с S. Добавляем полученные длины.
$SA=1$
$SB=2$
2) из соседедствующих вершин можем перейти куда-нибудь только из вершины B, значит имеем
$SBA=2-2=0 \leq SA=1$, все ребра проверены, оставшиеся пути кратчайшие пути

$SBA=0, SB=2$

Разве не нашёл этот путь?

-- 20.01.2015, 13:58 --

Или здесь суть в том, что дейкстра остановится, проверив все вершины и по третьему ребру даже не пройдёт?

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


18/01/13
12044
Казань
А мне кажется, что проблема начинается там, где есть циклы. Ведь при отрицательной длине цикла минимального пути просто не существует.

 Профиль  
                  
 
 Re: Алгоритм дейкстры
Сообщение20.01.2015, 13:07 
Заслуженный участник


20/07/09
4026
МФТИ ФУПМ
greg2 в сообщении #965449 писал(а):
1) смотрим все вершины, соседствующие с S. Добавляем полученные длины.
$SA=1$
$SB=2$
Вычёркиваем $S$. Смотрим на кратчайшего соседа — это $A$, из неё нельзя перейти, вычеркиваем её. Смотрим на $B$: у неё нет невычеркнутых соседей. Конец.

-- Вт янв 20, 2015 13:10:58 --

provincialka в сообщении #965459 писал(а):
А мне кажется, что проблема начинается там, где есть циклы. Ведь при отрицательной длине цикла минимального пути просто не существует.
Это немного не то. Одно дело нет пути, другое дело алгоритм не находит. Беллман-Форд находит путь при отрицательных весах и даже распознаёт отрицательные циклы, если я не ошибаюсь.

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


18/01/13
12044
Казань
Да, я уже сообразила.

 Профиль  
                  
 
 Re: Алгоритм дейкстры
Сообщение20.01.2015, 13:15 


30/11/14
54
Nemiroff в сообщении #965460 писал(а):
greg2 в сообщении #965449 писал(а):
1) смотрим все вершины, соседствующие с S. Добавляем полученные длины.
$SA=1$
$SB=2$
Вычёркиваем $S$. Смотрим на кратчайшего соседа — это $A$, из неё нельзя перейти, вычеркиваем её. Смотрим на $B$: у неё нет невычеркнутых соседей. Конец.


ну а допустим мы имеем такие длины ребер: $SA=3, SB=1, BA=1$. Дейкстра так же не должен будет перейти на А через B, хотя этот путь будет кратчайшим

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


18/01/13
12044
Казань
В этом случае сначала обрабатывается $B$, у нее метка меньше.

 Профиль  
                  
 
 Re: Алгоритм дейкстры
Сообщение20.01.2015, 13:19 


30/11/14
54
provincialka в сообщении #965468 писал(а):
В этом случае сначала обрабатывается $B$, у нее метка меньше.


Сначала же рассматриваются все соседи, а только потом продолжают рассматривают соседей соседей, начиная с "кратчайшего" соседа.

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


18/01/13
12044
Казань
На нулевом шаге вершине $S$ ставится в соответствие 0. Потом $A \to 3, B\to1$. Зачеркиваем $S$. Дальше что?

 Профиль  
                  
 
 Re: Алгоритм дейкстры
Сообщение20.01.2015, 13:23 


30/11/14
54
Всё, понял. Тут загвоздка в том, что это ориентированный граф и перейти с А мы никуда не можем, а с В можем. Тогда выходят для неориентированного графа отрицательные грани - не помеха алгоритму дейкстры?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 17 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

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