Алгоритм Дейкстры
Vložit
- čas přidán 19. 06. 2012
- Имеем ориентированный взвешенный граф. Ищем кратчайшие пути от одной из вершин до остальных. Вершинам задаем так называемые "временные" и "постоянные" метки. На каждом этапе наименьшая временная метка становится постоянной, от вершины с этой меткой на следующем этапе разыскиваются пути к доступным (соседним) вершинам. См. книгу Кирсанов М.Н. "Графы в Maple".
![[Vowel]물고기는 물에서 살아야 해🐟🤣Fish have to live in the water #funny](http://i.ytimg.com/vi/3G9MH063Cx4/mqdefault.jpg)
Большое спасибо. Это лучшее объяснение данного алгоритма, из тех что я встретил на просторах. Понятно и наглядно👍👍
Пасибо , что спасаете ленивых студентов..
Объяснение с прямой линией вижу в первый раз, и это очень удобно. Спасибо большое!
Вы сэкономили мне кучу времени. Спасибо!
Благодарю вас за информационный, легко усвоиемый видео урок.
Спасибо, всех благ вам за ваши труды :)
Спасибо большое! Очень доходчиво объясняете.
Большое спасибо,вам за ваши труды
Посмотрел куча других видео - ничего не понял. Посмотрел ваше - все понял с самого начала. Спасибо за доступное объяснение.
Спасибо за урок..Всё ясно и понятно!!)нет ничего лишнего - всё по теме!!
Отлично! Очень доходчиво. Спасибо!
Спасибо Вам большое, очень доступно и понятно объяснили.
Очень интересно и доходчиво, спасибо!
Большое спасибо,все понятно и доступно
Большое спасибо за доступное объяснение
Вы просто лучший
Благодаря вам , получил 90 баллов по дискретной математике. Спасибо!!!
спасибобольшое вам за очень простое обьяснение. здоровья и процветания вам
Спасибо огромное, уже столько времени прошло, а акутально и по сей день:)
Спасибо Вам огромное! Наконец-то окончательно разобрался с этим алгоритмом.
Спасибо большое вам за обьяснение!
Пересмотрел несколько раз, поставил лайк, алгоритм запомнил, идеально
Отличное объяснение) Спасибо!!
Всё отлично понятно, спасибо за видео)
Огромное спасибо! Вы помогли мне понять этот алгоритм!
Спасибо автору
Спасибо огромное!!!!!!!!!!!!!!
Хочу заметить, что алгоритм физически напоминает поведение воды когда она накапливается на неровном ландшафте, первым делом заливает пустоты, затем если вокруг высокие препятствия - ищет следующий кратчайший путь повышая уровень воды. Повышение уровня воды - это аналог "удорожания маршрута".
Спасибо большое!
Благодарю) Долго не мог понять, теперь разобрался)
Спасибо большое, все понятно)
Спасибо!
Спасибо!!!
Отличное представление!
просмотрите еще раз и почитайте книги... Успехов!
Для поиска последовательности узлов алгоритм надо еще немного доработать. Но не принципиально, просто на каждом этапе запоминать, из чего складывается минимальная сумма, а потом стирать ее, если найдется еще меньше (а в ней тоже уже хранится последовательность...). На любом алгоритм.языке это не трудно сделать. Я это делал в Maple (см. мою книгу "Графы в Maple", она есть в сети)
Мужик, спасиб большое
благодаря видео я сдела свою контрольную работу по графам))) спасибо БОЛЬШОЕ
+Дима Рекун Ради этого я и трудился...
Отлично! Разобрался с алгоритмом Дейсктры!
Нет ли у Вас такого же доступного урока по алгоритмам Форда и Флойда? Не могу разобраться.
Заранее благодарен!!!
Спасибо)
Спасибо, док.
Хорошо, нашли мы кратчайшее расстояние, а как узнать через какие точки? Из полученной таблицы я наглядно этого не увидел.
спасибо!
супер!
Спасибо. А если так?! Найти все пути из первой точки в последнюю; затем для каждого найденного пути найти расстояние; сохранить все в массиве, отсортировать массив расстояний по возрастанию, то первое значение и будет кратчайшим путём. Это уже будет далеко от алгоритма Дейкстры?!
Вот в том то и дело - как найти ВСЕ пути? Перебором? Думайте. Вопрос не закрыт. Алг Дейкстры - это одно из решений
@@Kirsanov2011вот такой у меня получился способ, (без кода) на основе упорядоченной матрицы: czcams.com/video/FBk5vDdusoY/video.html
Спасибо, все понятно. Но у нам в университете используют алгоритм из 6-ти ходов... То еще занятие, но результат тот же значит?
Спасибо большое взглянул на это с другой стороны
Спасибо.
Никак не мог разобраться, как работает протокол динамической маршрутизации OSPF, он как раз основан на методе Дейкстры. Посмотрел видео, разобрался. Спасибо)
Могли бы вы рассказать о методе Беллмана-Мура? Для отрицательных весов
Отличное видео, все очень понятно! Единственный вопрос, как вычислять сам путь (порядок вершин), а не только длину пути?
+Katty Rein Пишите каждый раз список предшествующих вершин
не могли бы пожалуйста, про D* еще рассказать
Огромное спасибо! Ни как не мог найти ошибку в своей реализации алгоритма=)
superb! spassibo!
Зачем блок-схема? Могу и саму программу на простом и понятном языке Maple. См. стр. 111 моей книги "Графы в Maple" (книга есть в сети, но уже нет в продаже). Но там задействованы и спец.команды Maple, хотя их назначение довольно ясно...
спасибо, тятя, вы очинь умнний. Я сам узбек делал поступило ни унивирсэтет. очинь сложна(((. вы памоч спосибо
Могли бы вы нарисовать блок схему к вашему решению и к алгоритму в целом??
Очень нужно!
Заранее спасибо!
Ничего не изменится, хоть 1000000! Можете еще алгоритмом Флойда воспользоваться, это еще проще, а потом свериться с Дейкстрой, все совпадет. Все эти алгоритмы доказываются, это только я так по-простому все рассказал... См. книги.
спасибо
Будет и Форд-Флойд. А Форд-Фалкерсон уже есть. Ищите.
Надо внимательнее, видио-гид очень подробно расписан: шаг за шагом. Спасибо за алгоритм!
А как найти сам путь, а не только его длину?
Как вариант - при обновлении метки сохранять информацию о вершине-предшественнике.
Я извиняюсь, просто посмотрел описание на Вики, и уж очень странным оно мне показалось. Под впечатлением, отправил сообщение не по адресу. Прошу извинить.
Я только одного момента не понял, алгоритм Дейкстры находит именно ВЕЛИЧИНУ пути, в вашем примере, это 5, либо он может найти сам путь, т.е. перечень всех узлов по порядку которые нужно посетить?
Назначь длиной каждого ребра единицу, тогда этот алгоритм выведет тебе наименьшее кол-во рёбер от начальной до конечной вершины, а это и есть маршрут.
Сделал лабу четверти группы, спасибо)
просто мне именно блок-схема нужна для курсовой работы
все объяснение ваше понял, а вот как нарисовать блок-схему не понимаю(
В рамках моей задачи, для поиска маршрута я могу использовать следующий подход - удалять из графа все длинные пути к одной и той-же вершине, оставляя только короткие. При вычислении веса вершины, если новый вес больше текущего, это значит, что найден дополнительный и более длинный путь к этой вершине. Следовательно этот путь (ребро) я могу удалить из графа. Для моей задачи это не критично. Таким образом в конце получаю граф в котором все точки связаны только одним маршрутом. Думаю это сработает.
Здравствуйте. А алгоритм флойда уошера у вас нет? Я ваши видео глянул но ничего такого не встретил. Заранее спасибо
Мэи с заставкой в начале звучит грандиозно
Теперь я понимаю, почему в универе частенько ничего не понимал, этож надо, на 75% видео сказать, я ошибся в самом начале, давайте я за 2 секунды все переделаю.
ок, буду дорабатывать. Спасибо.
С этой таблицей я запутался еще сильнее
См, например, мою книгу "Графы в Maple"
Спасибо за видео, всё понятно, но у меня вопрос, что делать если в конце 2 повторяется постоянная вершина 4 ?
Не совсем ясен вопрос. Постоянная вершина только один раз появляется. Потом ход на нее запрещен.
у меня повторяется наименьшее число
Если два одинаковых наименьших числа - берите любое.
Kirsanov2011 ясно, спасибо вам
@@Kirsanov2011 а что делать, если я пришла к определенной вершине (до конечной еще не дошла), но из нее ходы только в постоянные вершины, т.е. тупик?
Здравствуйте,этот алгоритм с первого раза приведет к кратчайшему пути?
Просто я для интереса выбрала не самый короткий путь на некоторых шагах а в итоге прошла более коротким путем чем если бы я действовала по алгоритму
Не может этого быть! Ошиблись.
@@Kirsanov2011 да,ошибка была в сносе,а где обзор на алгоритм Форда-Беллмана?
я не понял как он с вершины 3 в вершину 2 попал ?
+Дмитрий Вихарев , снес "2" с предыдущей строки так как она весит (мы её не прошли), и сравнил - минимальное в получившейся строчке
Спасибо, но я просто пытался вспомнить алгоритм.
Википедия расставила все на своим места
Вопрос такой. Если в одном ряду получилось два одинаковых числа и они оба наименьшие, то что делать?
Решение бывает не единственным. Поэтому берите любую. Потом для интереса возьмите другую.
А что делать если в ряду 2 одинаковые вершины?Решать относительно каждой?
Выбирать любую из них.
Спасибо за ролик в любом случае. но мне кажется надо это понимать на языке символов и алгоритмов. так для общего частного понимания средних к коим и себя отношу умов
имеем 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]
Ясно, алгоритм находит кратчайшее расстояние от одной вершины к остальным, а как быть если мне надо узнать не численное расстояние до остальных вершин, а маршрут (то есть список вершин чтобы в сумме удовлетворяли расстоянию) ?
Жалко, лектор этого не рассказал. Там нужно завести ещё один столбец, в котором указывать номер вершины, получившей постоянную пометку на данном шаге. С помощью этого столбца легко восстанавливается кратчайший путь до любой вершины. Также можно построить т.н. дерево кратчайших путей.
Находим минимальный путь, а если нужен максимальный путь выбираем на каждом шаге максимум? Спасибо
+Марина иванова Минимум функции f(x) совпадает с максимумом A-f(x) - просто перевернуть график
Можете подробней описать, как найти максимальний путь?
1. Берете какое-нибудь большое число А, большее, чем вес любой дуги графа.
2. Все веса f_k графа заменяете на A-f_k
3. В полученном графе находите минимальный путь. Для исходного графа он будет максимальным.
Благодарю за ответ!
Самое понятное разъяснение
Представленный алгоритм неполный, путь по вершинам, образующим минимальное расстояние не фиксируется. И вообще, объяснение не Дейкстры, родной алгоритм предусматривает обход по всем соседним вершинам, на которых еще не был. Далее Обход соседей от соседних вершин и т.д. ...
Спасибо!
Безусловно плюс за ваш труд, но, как мне кажется, не помешало бы сделать метку на видео когда начинается сам алгоритм :)
у нас в универе никогда не говорили "снести"
да это же элементарно! как можно запутаться?
Или хотя бы понятный алгоритм написать, по которому можно будет нарисовать блок-схему
спасибо огромное, у меня завтра экзамен по теории алгоритмов, надеюсь сдам)
Есть еще А*
Не понимаю, в вики описание отличается.
в вики графически представлено и псевдокодом
там тоже хорошая подача материала
Как найти максимальный путь
выбирай найбольшее значение в каждой строке.
слабо что-то понял, почему 5 если минимальное расстояние 1-3-6?
5 - это минимальное расстояние (минимальная сумма длин ребер), а не номер вершины, т.е длина ребра (1)->(3) = 1; длина ребра (3) -> (6) = 4. итого минимальное расстояние (1)->(3)->(6) = 1+4 = 5
Ааа зачем алгоритм дейскры если крускала быстрее
Алгоритм построения минимального остова? Зачем? или у Крускала есть еще алгоритм, который я не знаю?
чтобы дойти до вершины 6
и кстати за сколько работает алгоритм дейкстры
за квадрат или линию на логарифм
1) Алгоритм Крускала используется для построения минимального остова, а не для поиска кратчайших путей в орграфах.
2) Чтобы говорить об асимптотике алгоритма Дейкстры, нужно определиться со структурами данных, которые Вы собираетесь использовать.
В самой наивной реализации, если Вы будите хранить граф в виде матрицы смежности, то алгоритм будет работать за O(n^2), где n - число вершин графа. В самом деле, вам нужно будет сделать n шагов, на каждом из которых просматривать n вершин.
ничего не понял
Вообще то это и так видно что кратчайшее расстояние 5 данный зачем формализм?
а если там тысячи вершин?
Если владеете английском посмотрите вот сюда, /watch?v=xT5o1QCeWS8 - очень все четко объяснено.
Спасибо посмотрел
но вот же )))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
Мне эта инф знакома. Скоро будет новый вариант видео "Модификация алг Дейкстры".
угарный чел
Гладко было на бумаге...
А если вес 4-6 будет 1000, что этот алгоритм покажет?
Я ещё десяток графов могу нарисовать, в которых этот алгоритм не будет работать корректно.
Бестолково. И абсолютно бесполезно -- понять алгоритм из простой демонстрации его применения невозможно. Вот так надо объяснять: czcams.com/video/7oUt0zhv2sA/video.html