Почему алгоритм дейкстры не работает с ненаправленными графами?

Question

[Anther]

На многих источниках пишут, что алгоритм дейкстры не работает с циклами в графах, но объяснения не нашёл

Comments

[Wataru]

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

Answer 1

[Дмитрий]

Потому что алгоритм Дейкстры является "жадным алгоритмом".

Comments

[Anther]

Если это означает, что он найдёт более медленный способ, то можно пример, пожалуйста

[TAZAQ]

Fantoner, Это означает, что он зациклится (будет ходить по кругу)

Answer 2

[Lynn «Кофеман»]

> На многих источниках пишут

Например?

В википедии ничего такого нет. Есть только ограничение на неотрицательность весов.

Comments

[Anther]

алгоритм дейкстры работает только с графами вида DAG, то есть Directed Acyclic Graph. Прочёл в книжке Грокаем алгоритмы, а так же на многих сайтах

[Lynn «Кофеман»]

Fantoner, может мы о разных алгоритмах?
https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D...

[Wataru]

Fantoner, Бред. Вот на википедии прямо пример работы алгоритма - неориентированный граф с циклами.

Answer 3

[mayton2019]

Если под классического Дейкстру вы подсунете граф с циклами - то он зациклиться и никогда не выдаст ответа.

Что поделаешь. Таков он есть алгоритм. Но с другой стороны. Зачем вам решать задачу поиска кратчайших маршрутов на циклах? Поищите реальный пример из жизни и вы поймете что либо абстракция "не та" либо не тот алгоритм.

Comments

[Wataru]

Нет. Совсем нет! Дейкстра работает на циклах. Там на каждой итерации выбирается одна вершина, для которой фиксируется минимальное расстояние. Посмотрите на псевдокод в википедии, там внешний цикл с фиксированным количеством итераций! Дейкстра не может зациклится просто физически.

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

[mayton2019]

Я имел в виду ориентированный граф.