Алгоритм Дейкстры

Имеем ориентированный взвешенный граф. Ищем кратчайшие пути от одной из вершин до остальных. Вершинам задаем так называемые "временные" и "постоянные" метки. На каждом этапе наименьшая временная метка становится постоянной, от вершины с этой меткой на следующем этапе разыскиваются пути к доступным (соседним) вершинам. См. книгу Кирсанов М.Н. "Графы в Maple".

[@user-cy4lp7gn7p]

Большое спасибо. Это лучшее объяснение данного алгоритма, из тех что я встретил на просторах. Понятно и наглядно👍👍

[@senya5668]

Пасибо , что спасаете ленивых студентов..

[@annavasileva5688]

Объяснение с прямой линией вижу в первый раз, и это очень удобно. Спасибо большое!

[@osenyaaPechen]

Вы сэкономили мне кучу времени. Спасибо!

[@RomanOleynik92]

Благодарю вас за информационный, легко усвоиемый видео урок.

[@lif0CLUB]

Большое спасибо,вам за ваши труды

[@user-ls6ko9je3c]

Спасибо, всех благ вам за ваши труды :)

[@Enthe0genic]

Спасибо большое! Очень доходчиво объясняете.

[@user-go4kn1sy6u]

Спасибо за урок..Всё ясно и понятно!!)нет ничего лишнего - всё по теме!!

[@Faustism]

Отлично! Очень доходчиво. Спасибо!

[@user-ht1dy9pl7i]

Спасибо огромное, уже столько времени прошло, а акутально и по сей день:)

[@yehorpanchenko10]

Посмотрел куча других видео - ничего не понял. Посмотрел ваше - все понял с самого начала. Спасибо за доступное объяснение.

[@iluhanse745]

Спасибо Вам огромное! Наконец-то окончательно разобрался с этим алгоритмом.

[@ya_gema]

Спасибо Вам большое, очень доступно и понятно объяснили.

[@andrushabt]

спасибобольшое вам за очень простое обьяснение. здоровья и процветания вам

[@archwarden7004]

Очень интересно и доходчиво, спасибо!

[@leonidsah]

Вы просто лучший

[@user-wg8ty1rg1l]

Большое спасибо за доступное объяснение

[@user-sr8ss2er6r]

Огромное спасибо! Вы помогли мне понять этот алгоритм!

[@fogrinn7525]

Спасибо большое вам за обьяснение!

[@s4ygak]

Пересмотрел несколько раз, поставил лайк, алгоритм запомнил, идеально

[@ellviira]

Большое спасибо,все понятно и доступно

[@user-sh2qg9vk4u]

Отличное объяснение) Спасибо!!

[@raikhantemirova8951]

Благодаря вам , получил 90 баллов по дискретной математике. Спасибо!!!

[@MsTurugor]

Благодарю) Долго не мог понять, теперь разобрался)

[@valermann]

Отличное представление!

[@dailyInfo24]

спасибо, тятя, вы очинь умнний. Я сам узбек делал поступило ни унивирсэтет. очинь сложна(((. вы памоч спосибо

[@blk8722]

Всё отлично понятно, спасибо за видео)

[@Gidrionix]

Спасибо огромное!!!!!!!!!!!!!!

[@MySaluto]

Хочу заметить, что алгоритм физически напоминает поведение воды когда она накапливается на неровном ландшафте, первым делом заливает пустоты, затем если вокруг высокие препятствия - ищет следующий кратчайший путь повышая уровень воды. Повышение уровня воды - это аналог "удорожания маршрута".

[@user-ub5tj9th1m]

Спасибо автору

[@rusg777]

Спасибо большое!

[@user-ey5ch7vu1w]

благодаря видео я сдела свою контрольную работу по графам))) спасибо БОЛЬШОЕ

[@Kirsanov2011]

+Дима Рекун Ради этого я и трудился...

[@GAVVVR]

Спасибо большое, все понятно)

[@Kirsanov2011]

Для поиска последовательности узлов алгоритм надо еще немного доработать. Но не принципиально, просто на каждом этапе запоминать, из чего складывается минимальная сумма, а потом стирать ее, если найдется еще меньше (а в ней тоже уже хранится последовательность...). На любом алгоритм.языке это не трудно сделать. Я это делал в Maple (см. мою книгу "Графы в Maple", она есть в сети)

[@JeckPot111]

Мужик, спасиб большое

[@arthuralunts5424]

Спасибо, док.

[@DrRofl54]

Спасибо!

[@azazelluciferfuck]

Спасибо большое взглянул на это с другой стороны

[@treugolinik]

Спасибо!!!

[@Kirsanov2011]

просмотрите еще раз и почитайте книги... Успехов!

[@antontelyaev4927]

супер!

[@haruhiismygoddess2727]

Никак не мог разобраться, как работает протокол динамической маршрутизации OSPF, он как раз основан на методе Дейкстры. Посмотрел видео, разобрался. Спасибо)

[@user-yg7jf6jw7r]

Отлично! Разобрался с алгоритмом Дейсктры! Нет ли у Вас такого же доступного урока по алгоритмам Форда и Флойда? Не могу разобраться. Заранее благодарен!!!

[@user-of8fj1um1x]

Спасибо)

[@ablgmv]

спасибо!

[@vladimirduchenchuk8518]

Огромное спасибо! Ни как не мог найти ошибку в своей реализации алгоритма=)

[@sobolmx]

superb! spassibo!

[@trampller]

Спасибо.

[@kattyrein9900]

Отличное видео, все очень понятно! Единственный вопрос, как вычислять сам путь (порядок вершин), а не только длину пути?

[@Kirsanov2011]

+Katty Rein Пишите каждый раз список предшествующих вершин

[@user-lb7bg6tx3x]

Спасибо, все понятно. Но у нам в университете используют алгоритм из 6-ти ходов... То еще занятие, но результат тот же значит?

[@user-ih1mm4uv4m]

спасибо

[@Guveba]

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

[@Pancelet]

Мэи с заставкой в начале звучит грандиозно

[@Andrea13339]

Надо внимательнее, видио-гид очень подробно расписан: шаг за шагом. Спасибо за алгоритм!

[@Suuuuuuhovich]

Могли бы вы рассказать о методе Беллмана-Мура? Для отрицательных весов

[@Kirsanov2011]

Ничего не изменится, хоть 1000000! Можете еще алгоритмом Флойда воспользоваться, это еще проще, а потом свериться с Дейкстрой, все совпадет. Все эти алгоритмы доказываются, это только я так по-простому все рассказал... См. книги.

[@BbeeTV]

Могли бы вы нарисовать блок схему к вашему решению и к алгоритму в целом?? Очень нужно! Заранее спасибо!

[@jmnext1338]

Здравствуйте. А алгоритм флойда уошера у вас нет? Я ваши видео глянул но ничего такого не встретил. Заранее спасибо

[@FixedA]

не могли бы пожалуйста, про D* еще рассказать

[@SahkaP]

С этой таблицей я запутался еще сильнее

[@flukalpes]

А как найти сам путь, а не только его длину?

[@hskdjs]

Как вариант - при обновлении метки сохранять информацию о вершине-предшественнике.

[@dudejustdude]

Сделал лабу четверти группы, спасибо)

[@Kirsanov2011]

Зачем блок-схема? Могу и саму программу на простом и понятном языке Maple. См. стр. 111 моей книги "Графы в Maple" (книга есть в сети, но уже нет в продаже). Но там задействованы и спец.команды Maple, хотя их назначение довольно ясно...

[@AntonioNeStradivary]

Я извиняюсь, просто посмотрел описание на Вики, и уж очень странным оно мне показалось. Под впечатлением, отправил сообщение не по адресу. Прошу извинить. Я только одного момента не понял, алгоритм Дейкстры находит именно ВЕЛИЧИНУ пути, в вашем примере, это 5, либо он может найти сам путь, т.е. перечень всех узлов по порядку которые нужно посетить?

[@Kirsanov2011]

Будет и Форд-Флойд. А Форд-Фалкерсон уже есть. Ищите.

[@IvanGavr]

Спасибо. А если так?! Найти все пути из первой точки в последнюю; затем для каждого найденного пути найти расстояние; сохранить все в массиве, отсортировать массив расстояний по возрастанию, то первое значение и будет кратчайшим путём. Это уже будет далеко от алгоритма Дейкстры?!

[@Kirsanov2011]

Вот в том то и дело - как найти ВСЕ пути? Перебором? Думайте. Вопрос не закрыт. Алг Дейкстры - это одно из решений

[@IvanGavr]

@@Kirsanov2011вот такой у меня получился способ, (без кода) на основе упорядоченной матрицы: kzbin.info/www/bejne/fHPOZql6mdqmpbs

[@batista12001]

Назначь длиной каждого ребра единицу, тогда этот алгоритм выведет тебе наименьшее кол-во рёбер от начальной до конечной вершины, а это и есть маршрут.

[@AntonioNeStradivary]

ок, буду дорабатывать. Спасибо.

[@AntonioNeStradivary]

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

[@user-zm2lx8ly2j]

Здравствуйте,этот алгоритм с первого раза приведет к кратчайшему пути? Просто я для интереса выбрала не самый короткий путь на некоторых шагах а в итоге прошла более коротким путем чем если бы я действовала по алгоритму

[@Kirsanov2011]

Не может этого быть! Ошиблись.

[@user-zm2lx8ly2j]

@@Kirsanov2011 да,ошибка была в сносе,а где обзор на алгоритм Форда-Беллмана?

[@gudapavella1751]

Теперь я понимаю, почему в универе частенько ничего не понимал, этож надо, на 75% видео сказать, я ошибся в самом начале, давайте я за 2 секунды все переделаю.

[@user-xb7fs2uc4f]

Вопрос такой. Если в одном ряду получилось два одинаковых числа и они оба наименьшие, то что делать?

[@Kirsanov2011]

Решение бывает не единственным. Поэтому берите любую. Потом для интереса возьмите другую.

[@SahkaP]

Спасибо, но я просто пытался вспомнить алгоритм. Википедия расставила все на своим места

[@Kirsanov2011]

См, например, мою книгу "Графы в Maple"

[@AngelVlad100]

А что делать если в ряду 2 одинаковые вершины?Решать относительно каждой?

[@Kirsanov2011]

Выбирать любую из них.

[@alexandristomin2410]

Спасибо за видео, всё понятно, но у меня вопрос, что делать если в конце 2 повторяется постоянная вершина 4 ?

[@Kirsanov2011]

Не совсем ясен вопрос. Постоянная вершина только один раз появляется. Потом ход на нее запрещен.

[@alexandristomin2410]

у меня повторяется наименьшее число

[@Kirsanov2011]

Если два одинаковых наименьших числа - берите любое.

[@alexandristomin2410]

Kirsanov2011 ясно, спасибо вам

[@fenrrisulfr]

@@Kirsanov2011 а что делать, если я пришла к определенной вершине (до конечной еще не дошла), но из нее ходы только в постоянные вершины, т.е. тупик?

[@mcd-ti2wv]

Самое понятное разъяснение

[@dizogdizog2591]

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

[@MaximumDo]

имеем 2 массива: дист[n] = [0]*n, tested[n] = [false]*n и матрица смежности am[n][n], где, если вершины не связаны, стоит inf пока минимальная длина < inf tested[minvert] = true для всех вершин графа если dist[minvert] + am[minvert][i] < dist[i] обновляем dist[i] ищем вершину с наименьшим дист[i] и tested[i] == false minvert = i mindist = dist[i]

[@user-bb4xz2ok7z]

спасибо огромное, у меня завтра экзамен по теории алгоритмов, надеюсь сдам)

[@Kirsanov2011]

Есть еще А*

[@kyzmitch2]

у нас в универе никогда не говорили "снести"

[@user-wm8st2ni4x]

Находим минимальный путь, а если нужен максимальный путь выбираем на каждом шаге максимум? Спасибо

[@Kirsanov2011]

+Марина иванова Минимум функции f(x) совпадает с максимумом A-f(x) - просто перевернуть график

[@Ilichi]

Можете подробней описать, как найти максимальний путь?

[@Kirsanov2011]

1. Берете какое-нибудь большое число А, большее, чем вес любой дуги графа. 2. Все веса f_k графа заменяете на A-f_k 3. В полученном графе находите минимальный путь. Для исходного графа он будет максимальным.

[@Ilichi]

Благодарю за ответ!

[@kriguitar4753]

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

[@bond94g]

Жалко, лектор этого не рассказал. Там нужно завести ещё один столбец, в котором указывать номер вершины, получившей постоянную пометку на данном шаге. С помощью этого столбца легко восстанавливается кратчайший путь до любой вершины. Также можно построить т.н. дерево кратчайших путей.

[@BbeeTV]

просто мне именно блок-схема нужна для курсовой работы все объяснение ваше понял, а вот как нарисовать блок-схему не понимаю(

[@lerby5512]

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

[@dm.vortex4171]

я не понял как он с вершины 3 в вершину 2 попал ?

[@user-sf1pm4jz4j]

+Дмитрий Вихарев , снес "2" с предыдущей строки так как она весит (мы её не прошли), и сравнил - минимальное в получившейся строчке

[@traxternberg]

Представленный алгоритм неполный, путь по вершинам, образующим минимальное расстояние не фиксируется. И вообще, объяснение не Дейкстры, родной алгоритм предусматривает обход по всем соседним вершинам, на которых еще не был. Далее Обход соседей от соседних вершин и т.д. ...

[@Kirsanov2011]

Спасибо!

[@DimaasisDas]

да это же элементарно! как можно запутаться?

[@Suuuuuuhovich]

Как найти максимальный путь

[@MrProdagi]

выбирай найбольшее значение в каждой строке.

[@vasyapupkin997]

угарный чел

[@ekklesiast]

Не понимаю, в вики описание отличается.

[@Das.Kleine.Krokodil]

в вики графически представлено и псевдокодом там тоже хорошая подача материала

[@BbeeTV]

Или хотя бы понятный алгоритм написать, по которому можно будет нарисовать блок-схему

[@Inseidful]

слабо что-то понял, почему 5 если минимальное расстояние 1-3-6?

[@IvanShulga]

5 - это минимальное расстояние (минимальная сумма длин ребер), а не номер вершины, т.е длина ребра (1)->(3) = 1; длина ребра (3) -> (6) = 4. итого минимальное расстояние (1)->(3)->(6) = 1+4 = 5

[@dizogdizog2591]

Спасибо посмотрел но вот же )))ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B

[@Kirsanov2011]

Мне эта инф знакома. Скоро будет новый вариант видео "Модификация алг Дейкстры".

[@mkdotam]

Если владеете английском посмотрите вот сюда, /watch?v=xT5o1QCeWS8 - очень все четко объяснено.

[@user-jg3xw2hs7i]

Ааа зачем алгоритм дейскры если крускала быстрее

[@Kirsanov2011]

Алгоритм построения минимального остова? Зачем? или у Крускала есть еще алгоритм, который я не знаю?

[@user-jg3xw2hs7i]

чтобы дойти до вершины 6

[@user-jg3xw2hs7i]

и кстати за сколько работает алгоритм дейкстры

[@user-jg3xw2hs7i]

за квадрат или линию на логарифм

[@dmitrypetrov8491]

1) Алгоритм Крускала используется для построения минимального остова, а не для поиска кратчайших путей в орграфах. 2) Чтобы говорить об асимптотике алгоритма Дейкстры, нужно определиться со структурами данных, которые Вы собираетесь использовать. В самой наивной реализации, если Вы будите хранить граф в виде матрицы смежности, то алгоритм будет работать за O(n^2), где n - число вершин графа. В самом деле, вам нужно будет сделать n шагов, на каждом из которых просматривать n вершин.

[@user-ui5ob8cu5u]

Вообще то это и так видно что кратчайшее расстояние 5 данный зачем формализм?

[@juneority]

а если там тысячи вершин?

[@john1987742]

ничего не понял

[@Leha900]

Он один из тех преподавателей, которому если самому ясно, то и ладно, а как там ученики, его не очень волнует. Пропускает детали в объяснении.

[@AntonioNeStradivary]

Гладко было на бумаге... А если вес 4-6 будет 1000, что этот алгоритм покажет? Я ещё десяток графов могу нарисовать, в которых этот алгоритм не будет работать корректно.