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

[@Денис-р5в4з]

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

[@senya5668]

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

[@annavasileva5688]

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

[@osenyaaPechen]

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

[@yehorpanchenko10]

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

[@iluhanse745]

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

[@КристинаМищенко-з1м]

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

[@leonidsah]

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

[@raikhantemirova8951]

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

[@RomanOleynik92]

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

[@vrakitine]

В институте я много слышал про конечные автоматы (КА), но это всё было теорией - как облака в небе: воды в них много, а напиться нельзя. Корпел три месяца после института, пока не реализовал свой КА в коде в 1981 году. Сейчас существует методология программирования на этой основе - v-agent oriented programming (VAOP) - и множество примеров её реализации. Лучше начать знакомство с VAOP с этой статьи на Medium: "Bagels and Muffins of Programming or How Easy It Is to Convert a Bagel into a Black Hole" или на Хабре: "Бублики и Коржики Программирования".

[@НиколайХодарев-ь8н]

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

[@andrushabt]

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

[@s4ygak]

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

[@Faustism]

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

[@dailyInfo24]

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

[@lif0CLUB]

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

[@MySaluto]

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

[@arthuralunts5424]

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

[@ДимаРекун-ю8т]

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

[@Kirsanov2011]

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

[@MsTurugor]

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

[@Enthe0genic]

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

[@IvanGavr]

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

[@Kirsanov2011]

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

[@IvanGavr]

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

[@valermann]

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

[@fogrinn7525]

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

[@Kirsanov2011]

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

[@КатяБабчинская-ю5ш]

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

[@archwarden7004]

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

[@АртёмЧацкий-э9в]

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

[@Мурчащиекотятки]

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

[@KartDev]

Пока что самое понятное объяснение, которое я встречал в инете

[@Guveba]

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

[@ustesrendel]

А для чего добавлять значение предыдущей метки?

[@haruhiismygoddess2727]

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

[@Kirsanov2011]

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

[@ya_gema]

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

[@ellviira]

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

[@АртёмТютюнник-ы7р]

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

[@kattyrein9900]

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

[@Kirsanov2011]

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

[@micebirds]

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

[@ЮлияКравцова-о6ф]

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

[@JeckPot111]

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

[@Pancelet]

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

[@flukalpes]

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

[@hskdjs]

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

[@Gidrionix]

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

[@СергейБренько-ы3л]

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

[@FixedA]

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

[@SahkaP]

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

[@Suuuuuuhovich]

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

[@antontelyaev4927]

супер!

[@rusg777]

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

[@mcd-ti2wv]

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

[@vladimirduchenchuk8518]

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

[@Kirsanov2011]

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

[@blk8722]

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

[@gudapavella1751]

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

[@jmnext1338]

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

[@AntonioNeStradivary]

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

[@Денис-з7ч]

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

[@Kirsanov2011]

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

[@batista12001]

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

[@AngelVlad100]

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

[@Kirsanov2011]

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

[@Kirsanov2011]

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

[@ЛюссанаБазарова]

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

[@Kirsanov2011]

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

[@ЛюссанаБазарова]

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

[@BbeeTV]

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

[@Kirsanov2011]

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

[@treugolinik]

Спасибо!!!

[@GAVVVR]

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

[@sobolmx]

superb! spassibo!

[@Kirsanov2011]

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

[@BbeeTV]

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

[@trampller]

Спасибо.

[@Маринаиванова-ф9ь]

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

[@Kirsanov2011]

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

[@Ilichi]

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

[@Kirsanov2011]

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

[@Ilichi]

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

[@dm.vortex4171]

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

[@МишаОвчинников-ц8й]

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

[@kyzmitch2]

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

[@Andrea13339]

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

[@Suuuuuuhovich]

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

[@aivashyna]

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

[@ablgmv]

спасибо!

[@ВалентинТятьков]

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

[@БабкаБомБом]

Спасибо)

[@alexandristomin2410]

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

[@Kirsanov2011]

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

[@alexandristomin2410]

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

[@Kirsanov2011]

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

[@alexandristomin2410]

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

[@fenrrisulfr]

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

[@ЮлияЛапина-ц4л]

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

[@Kirsanov2011]

Есть еще А*

[@gitarnoob]

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

[@bond94g]

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

[@traxternberg]

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

[@Kirsanov2011]

Спасибо!

[@AntonioNeStradivary]

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

[@ПетрАвен-к7ч]

спасибо

[@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]

[@lerby5512]

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

[@ekklesiast]

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

[@Das.Kleine.Krokodil]

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

[@john1987742]

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

[@dudejustdude]

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

[@AntonioNeStradivary]

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

[@SahkaP]

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

[@BbeeTV]

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

[@АлександрБирич-щ2с]

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

[@Kirsanov2011]

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

[@АлександрБирич-щ2с]

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

[@АлександрБирич-щ2с]

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

[@АлександрБирич-щ2с]

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

[@dmitrypetrov8491]

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

[@ПррроРос]

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

[@juneority]

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

[@Inseidful]

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

[@IvanShulga]

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

[@DimaasisDas]

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

[@padla6304]

4.5 < 5

[@vasyapupkin997]

угарный чел

[@mkdotam]

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