Обсуждение:Алгоритм Дейкстры

Корректность

Цикл завершается, когда флаги всех вершин становятся равны 1, либо когда у всех вершин c флагом 0 d [ i ] = ∞ {\displaystyle d[i]=\infty } d[i]=\infty . Последний случай возможен тогда и только тогда, когда граф G несвязный.

Корректно ли это? Если флаг - это признак посещённой вершины, всегда существуют вершины, у которых "флаг" равен нулю, до обхода всех вершин. И, при этом, их вес (после этапа инициализации) равен бесконечности. Т.е., по данному условию, алгоритм должен завершиться после инициализации: надо бы условие переформулировать более корректно.

Иначе, поскольку сейчас выбрана вершина z, а не y, метка z минимальна среди непосещённых, то есть $d(z)\leq d(y)=l(y)\leq l(z)$. Комбинируя это с $d(z)\geq l(z)$, имеем $d(z)=l(z)$, что и требовалось доказать.

Может всё-таки знак обратен?

$d(z)\geq d(y)=l(y)\leq l(z)$ 91.195.22.23 15:26, 19 сентября 2016 (UTC)

Untitled

Абсолютно кривая реализация алгоритма под Delphi, полностью удалил --MDA 14:31, 7 июля 2008 (UTC)

Уточните пожалуйста, как свести задачу о сортировке чисел к задаче о поиске кратчайших путей из одной вершины. --MDA 13:37, 7 июля 2008 (UTC)

формула O(V^2) отображалась с ошибкой. Исправил. T0ljan 17:53, 19 апреля 2006 (UTC)

Какой ошибкой? Мне $O(V^{2})$ нравится гораздо больше, чем O($V^{2}$). halyavin 18:05, 19 апреля 2006 (UTC)

У меня неправильно отображалось, какая-то лажа красным писалась, типа: Error че-то там math  :( Кстати, было бы неплохо по всем основным алгоритмам статьи сделать :) На досуге. Заодно сам их лучьше поймешь... T0ljan 18:46, 19 апреля 2006 (UTC)

"...города Львовской области" :) T0ljan 18:49, 19 апреля 2006 (UTC)

В таком случае меняю формулу назад. halyavin 04:14, 20 апреля 2006 (UTC)

Проверте пожалуйста значения вершины 4... dr.termit

Мда, что-то не то... Кто умеет фотошопом пользоваться? halyavin 10:07, 25 июня 2006 (UTC)

Что не так? На вид всё правильно. --Джус 15:47, 9 августа 2007 (UTC)

Да вот как раз на втором шаге в начале... Ближайшая вершина - третья. А выбирается почему-то четвертая. Непорядок... Перерисовать? --Aldekein 09:33, 24 января 2009 (UTC)

По-моему, порядок, в котором расставляются веса вершинам, смежным данной, не важен. Важен порядок перехода от вершине к вершине - по кратчайшему пути. Правильно? mookee 07:28, 16 июля 2009 (UTC)

Spasibo lyudi. Eto, namnogo legche ponyat chem shto napisano na angliskoi wikipedia (Ya tam nichego ne ponyal). A zdec' vse napisano tak prekrasno. Mozhet buyt' dazhe stoyet perepesat' tu.. --128.227.248.195 17:29, 27 сентября 2006 (UTC)

Дейкстра, Эдсгер Вайб это тот самый Дейкстра, или нет?--Vaya 11:08, 13 ноября 2006 (UTC)

Да, тот самый. stassats 03:15, 17 ноября 2006 (UTC)

В английской википедии алгоритм не просто $d[u]$ для $\forall u$ находит, но и непосредственно ищет сами кратчайшие пути от данной вершины ко всем остальным. --Джус 15:47, 9 августа 2007 (UTC)

Что-то типа этого [1]. Для примера я другой граф там взял. Можно бы переделать под тот, на котором в статье уже объясняется алгоритм, просто там одни цифры и в таблице ничего не понятно будет. --Джус 08:35, 10 августа 2007 (UTC)

математики любят через табличку этот алгоритм решать. Не подскажите как это делается?

Математики вообще любят ковыряться в носу крестовой отверткой и прочими способами усложнять жизнь. Если по теме, то... заменям граф на табличку, из расчета одна вершина -- одна клетка. Договариваемся записывать туда "текущее" минимальное расстояние до вершины. Пишем карандашем во все клетки, кроме исходной вершины "бесконечность". В исходной рисуем "ноль", причем ручкой. Лучше красной. И поехали по алгоритму -- среди "не красных" клеток берем ту, в которой число меньше; раскрашиваем ее в красный цвет, и пытаемся уменьшить число во всех клетках, вершины которых связаны с той, которую мы только что сделали красной. Так пока все клетки не будут красными.

Если нет красной ручки, то рисуем под первой таблицей еще одну. В ней будем рисовать крестики под теми клетками, которые должны быть красными.

Заголовок "Формальная формулировка", по-моему, звучит примерно также, как "Копательная лопата" :) Исправил на "Формальное определение". То же самое и с "неформальной". Есть возражения?

порядок выбора вершин, смежных данной (имеет ли он смысл?)

Как уже было отмечено в сообщении mookee 07:28, 16 июля 2009 (UTC), кажется, нет смысла в выборе вершин смежных данной в определенном порядке (их можно перебирать без какого-либо порядка).

По этой причине предлагаю изменить фразу: "Первый по очереди сосед вершины 1 — вершина 2, потому что длина пути до неё минимальна." [раздел 2, "Неформальное объяснение", подраздел "Пример", часть описания примера "Первый шаг", второй абзац (после первого рисунка первого шага)] - на что-нибудь вроде: "В качестве первого соседа вершины 1 можно взять вершину 2 (порядок перебора соседей не важен)." - а также фразу: "Следующий сосед вершины 2 — вершина 3, так имеет минимальную метку из вершин, отмеченных как не посещённые." [раздел 2, "Неформальное объяснение", подраздел "Пример", часть описания примера "Второй шаг", второй абзац 4 (после первого рисунка второго шага)] - на: "В качестве следующего соседа вершины 2 можно выбрать вершину 3."

Более того, псевдокод из раздела 3 ("Алгоритм"), из подраздела "Псевдокод" иллюстрирует тот факт, что порядок выбора вершин смежных данной не важен: "Для всех вершин υ, не принадлежащих множеству U, таких, что ребро υv принадлежит множеству ребер Е" (т.е. никакого намека на порядок перебора таких вершин). Равно не содержит никакой информации по порядку перебора таких вершин и неформальное описание шага алгоритма [раздел 2, "Неформальное объяснение", подзаголовок "Шаг алгоритма].

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

P.S. Согласен с возможными оговорками, что порядок перебора таких вершин может иметь смысл для конкретных реализаций алгоритма (оговорив порядок, может быть проще написать реализацию). Mopk 09:40, 24 июня 2010 (UTC)

о доказательстве того, что расстояние до вершины 1 считается окончательным и пересмотру не подлежит

Кажется бессмысленным пояснение (в круглых скобках) к фразе: "Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит (то, что это действительно так, впервые доказал Э. Дейкстра)." [раздел 2, "Неформальное объяснение", подраздел "Пример", часть описания примера "Первый шаг", четвертый абзац (после третьего рисунка первого шага)]

Предлагаю заменить на: "Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит."

Постановка задачи, которую решает алгоритм Дейкстры: "Дан взвешенный ориентированный граф без петель и дуг отрицательного веса. Найти кратчайшие пути от некоторой вершины графа до всех остальных вершин этого графа." Т.о. доказывать такой тривиальный факт (что минимальное расстояние от вершины до самой себя является 0-вым, окончательным и пересмотру не подлежит) вряд ли было нужно. С трудом верю, что Дейкстра действительно потратил время на столь же тривиальное доказательство этого (тривиального) факта. Этот факт не требует доказательства даже в случае графов с петлями. Единственным условием, которое бы могло поменять эту ситуацию, было бы условие, что граф - с отрицательными ребрами. Но это условие исключено на этапе постановки задачи. Mopk 10:01, 24 июня 2010 (UTC)

Mopk, я ваc поправлю - вы сказали: "Дан взвешенный ориентированный граф без петель и дуг отрицательного веса. Найти кратчайшие пути от некоторой вершины графа до всех остальных вершин этого графа.", а в статье дан другой граф, и надо говорить: "Дан взвешенный не ориентированный граф без петель и дуг отрицательного веса. Найти кратчайшие пути от некоторой вершины графа до всех остальных вершин этого графа." Ллирик 12:06, 2 мая 2011 (UTC)

В статье нужен пример с ориентированным графом и запоминанием пути. Тогда вопросы [2] возникать не будут.--Anton Khorev 18:13, 2 мая 2011 (UTC)

А разве ориентированность графа как-то меняет ситуацию? AVL 93 12:54, 9 мая 2011 (UTC)

На статью влияет. Сейчас в статье вот что:

• Введение: расстояние до всех
• Вариант 1: путь до всех на ориентированном
• Вариант 2: путь до одной (о чём не говорится) на ориентированном
• Формальное определение: путь до всех на ориентированном
• Анимация: расстояние до одной на неориентированном
• Пример: расстояние (которое называют "путём" в конце раздела) до всех на неориентированном
• Алгоритм: пытается получить и расстояние и путь в псевдокоде, но в описании про путь не говорится

--Anton Khorev 00:18, 10 мая 2011 (UTC)

Непонятное действие в псевдокоде

Или это я что-то не понимаю, но мне эта строка кажется бессмысленной:

изменим $p[u]\gets p[v],u$

Что значит выражение $p[u]\gets p[v],u$? Что конкретно мы присваиваем $p[u]$? Шадрин Денис 17:56, 5 марта 2011 (UTC)

[3] имеется в виду вот что:

• для тех вершин, до которых алгоритм добрался, в p[v] находится список вершин a,...,v, являющийся путём от a до v
• p[v], u означает создать копию пути p[v] и добавить в его конец u
• если вершина недостижима, то при завершении алгоритма в p[u] будет неизвестно что, потому что его ничем не инициализировали (нам обещают, что там будет кратчайший путь от a)
• но алгоритм никогда не завершится, потому что добавление вершины ко множеству посещённых снесли [4]

--Anton Khorev 17:54, 2 мая 2011 (UTC)

Создавать копию нельзя, это утяжеляет алгоритм. Надо переписать, чтобы было как везде - p[x] хранит предшественника вершины x на кратчайшем пути до корня, и присваивание должно быть просто p[u] := v. Сам кратчайший путь восстанавливают отдельным циклом по массиву предшественников по завершении алгоритма. Также тут можно рассказать что-нибудь про дерево кратчайших путей. -- X7q 18:14, 2 мая 2011 (UTC)

Надо переписать, чтобы было понятно, что если мы ищем расстояние (во введении нам говорят, что алгоритм ищет расстояние), то p вообще не нужен.--Anton Khorev 21:28, 2 мая 2011 (UTC)

Предлагаю также заменить стрелки на := в алгоритме. Намного более понятная и распространённая нотация, чем эти стрелки из второго издания Кормена (в 3-м издании они тоже от них отказались). -- X7q 18:20, 2 мая 2011 (UTC)

Глупый вопрос к знатокам

У меня глупый вопрос к знатокам. Пишу реализацию для "сильно разветвленного и очень запутанного" графа. Графическое пояснение алгоритма в этой статье не объясняет например, как найти все пути в графе, вершины которого соеденены ребрами в форму "кольца", т.е. каждая вершина - 2 степени, т.е. каждая вершина соединена со следующей в порядке возрастания их номеров, и последний номер вершины смежен с первым. Существует формальный алгоритм для такого случая?
Вот ситуация в таком графе(предположим 9 вершин):
Предположим мы производим замеры пути к вершине 9 от вершины 8. вершина 7 посещена и пересмотру не подлежит (это на 1 шаге мы пошли на метку номер 2, так как оказалось, что d(9)>d{2) ). Сейчас, находясь на 8 вершине видим, что d(8)+w(89)>d(9), поэтому метку 9 вершины естесственно не меняем. Но очень хочется переписать метку восьмой вершины, т.к. d(9)+w(98)намного меньше вычисленного прежде d(8). После такого переопределения хочеться переписать и метку с номером 7, т.к. оказывается, что d(8)+w(87)<d(7), но этого уже нельзя - она вычеркнута и пересмотру не подлежит. Как поступить?
PS: w() - ребро, d() - путь, пройденый до вершины.
Ллирик 13:03, 2 мая 2011 (UTC)

Дейкстра и не ищет все пути в графе. Только пути из заданной вершины (или в заданную вершину, как вариант). Для кольца Дейкстра даже не нужна. Между любой парой вершин там всего два пути, длины которых легко вычисляются за константу после линейной предобработки. Если вам хочется дважды пересмотреть вершину то, вероятно, вы не совсем правильно поняли суть алгоритма. Однако ввиду ВП:НЕФОРУМ не следует углубляться в обсуждение этого вопроса на данной странице. Если хотите, напишите мне в личку, приведите граф и я попытаюс указать на ошибку. -- X7q 18:37, 2 мая 2011 (UTC)

Снимаю вопрос с обсуждения. Разобрался. X7q, вы не правы. Алгоритм работает как для кольцевого графа, так и для всех остальных и ищет все пути.--Ллирик 13:50, 3 мая 2011 (UTC)

Отличный Алгоритм, жаль, что неправильный

[5]

Как быть с таким графом? Что в данном случае найдёт описанный алгоритм - какой-нибудь (какой получилось) путь? Видимо описание алгоритма неверное или неполное.

90.155.241.194 21:12, 10 июня 2013 (UTC)Антон

Прочитайте внимательно шаг алгоритма. Он состоит из двух этапов, сначала выбирается ближвйшая непосещённая вершина, затем проиходит релаксация, то есть для всех непосещённых вершин j, являющихся соседями i, как ответ записывается min(Ans[j], Ans[i] + len(i->j)). Ваш граф отличается только одним ребром, и всё отличие в работе алгоритма будет в том, что сначала в 6 вершину из 4 запишется одно значение, а затем в 5 вершине оно срелаксируется в правильное. --Real-vient 16:44, 19 августа 2014 (UTC)

Немного неудачный граф в примере

У некоторых может сложиться впечатление, что алгоритм просто переходит от вершины к вершине, каждый раз выбирая кратчайшее ребро. См. вопрос на SO.

Dzhioev 07:06, 9 октября 2015 (UTC)

В примере не помешало бы выделить ребра для наглядности.178.168.130.8 11:36, 10 августа 2016 (UTC)Andrey

Не загружается картинка

То пишет, что вредоносная, то неподходящая по W#iki commons. Я рисовала ее в пейнте. ЧЯДНТ? :(((

Wera

• @Wera: сложно сказать. На каком этапе возникает проблема, и что именно говорит сообщение об ошибке? — Алексей Копылов 15:33, 24 марта 2019 (UTC)

Противоречие

С одной стороны в неформальном описании говорится, что работа алгоритма заканчивается, когда все вершины посещены. И в конце оговорка, что в случае несвязного графа все вершины могут быть и не посещены. Какой-то универсальный критерий завершения алгоритма есть?

• Уточнил. — Алексей Копылов 21:06, 9 мая 2019 (UTC)
  • Алгоритм «находит кратчайшие пути от одной из вершин графа до всех остальных.» — то есть, видимо имеется в виду, что все вершины внутри компоненты связности. Противоречия нет. Наличие других компонент не мешает получению результата (там отметки «бесконечность»). РоманСузи (обс.) 15:00, 10 мая 2019 (UTC)

Код на Java не такой

В коде используется внешние классы, определение которых не приводится. Например Edge. Надо что-то с этим делать. ~~~Morphius

89.249.231.157 15:15, 1 сентября 2024 (UTC)