Алгоритм Дейкстры
ฝัง
- เผยแพร่เมื่อ 29 พ.ย. 2024
- Имеем ориентированный взвешенный граф. Ищем кратчайшие пути от одной из вершин до остальных. Вершинам задаем так называемые "временные" и "постоянные" метки. На каждом этапе наименьшая временная метка становится постоянной, от вершины с этой меткой на следующем этапе разыскиваются пути к доступным (соседним) вершинам. См. книгу Кирсанов М.Н. "Графы в Maple".
![SAFEPLANET - ดาวเคราะห์ [ THE PLANET ]](http://i.ytimg.com/vi/4X1XL3I_k3c/mqdefault.jpg)
Большое спасибо. Это лучшее объяснение данного алгоритма, из тех что я встретил на просторах. Понятно и наглядно👍👍
Пасибо , что спасаете ленивых студентов..
Объяснение с прямой линией вижу в первый раз, и это очень удобно. Спасибо большое!
Посмотрел куча других видео - ничего не понял. Посмотрел ваше - все понял с самого начала. Спасибо за доступное объяснение.
Вы сэкономили мне кучу времени. Спасибо!
Благодаря вам , получил 90 баллов по дискретной математике. Спасибо!!!
Спасибо Вам огромное! Наконец-то окончательно разобрался с этим алгоритмом.
В институте я много слышал про конечные автоматы (КА), но это всё было теорией - как облака в небе: воды в них много, а напиться нельзя. Корпел три месяца после института, пока не реализовал свой КА в коде в 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" или на Хабре: "Бублики и Коржики Программирования".
Огромное спасибо! Вы помогли мне понять этот алгоритм!
спасибобольшое вам за очень простое обьяснение. здоровья и процветания вам
Благодарю вас за информационный, легко усвоиемый видео урок.
благодаря видео я сдела свою контрольную работу по графам))) спасибо БОЛЬШОЕ
+Дима Рекун Ради этого я и трудился...
Вы просто лучший
Пересмотрел несколько раз, поставил лайк, алгоритм запомнил, идеально
Спасибо огромное, уже столько времени прошло, а акутально и по сей день:)
Большое спасибо,вам за ваши труды
Хочу заметить, что алгоритм физически напоминает поведение воды когда она накапливается на неровном ландшафте, первым делом заливает пустоты, затем если вокруг высокие препятствия - ищет следующий кратчайший путь повышая уровень воды. Повышение уровня воды - это аналог "удорожания маршрута".
Отлично! Очень доходчиво. Спасибо!
Спасибо за урок..Всё ясно и понятно!!)нет ничего лишнего - всё по теме!!
Для поиска последовательности узлов алгоритм надо еще немного доработать. Но не принципиально, просто на каждом этапе запоминать, из чего складывается минимальная сумма, а потом стирать ее, если найдется еще меньше (а в ней тоже уже хранится последовательность...). На любом алгоритм.языке это не трудно сделать. Я это делал в Maple (см. мою книгу "Графы в Maple", она есть в сети)
Спасибо большое! Очень доходчиво объясняете.
просмотрите еще раз и почитайте книги... Успехов!
Большое спасибо за доступное объяснение
Спасибо Вам большое, очень доступно и понятно объяснили.
Очень интересно и доходчиво, спасибо!
Спасибо большое вам за обьяснение!
Спасибо, всех благ вам за ваши труды :)
Никак не мог разобраться, как работает протокол динамической маршрутизации OSPF, он как раз основан на методе Дейкстры. Посмотрел видео, разобрался. Спасибо)
спасибо, тятя, вы очинь умнний. Я сам узбек делал поступило ни унивирсэтет. очинь сложна(((. вы памоч спосибо
Спасибо, док.
Большое спасибо,все понятно и доступно
Пока что самое понятное объяснение, которое я встречал в инете
Благодарю) Долго не мог понять, теперь разобрался)
Отличное представление!
Спасибо. А если так?! Найти все пути из первой точки в последнюю; затем для каждого найденного пути найти расстояние; сохранить все в массиве, отсортировать массив расстояний по возрастанию, то первое значение и будет кратчайшим путём. Это уже будет далеко от алгоритма Дейкстры?!
Вот в том то и дело - как найти ВСЕ пути? Перебором? Думайте. Вопрос не закрыт. Алг Дейкстры - это одно из решений
@@Kirsanov2011вот такой у меня получился способ, (без кода) на основе упорядоченной матрицы: th-cam.com/video/FBk5vDdusoY/w-d-xo.html
Спасибо большое, всё очень понятно!
Отличное видео, все очень понятно! Единственный вопрос, как вычислять сам путь (порядок вершин), а не только длину пути?
+Katty Rein Пишите каждый раз список предшествующих вершин
Отличное объяснение) Спасибо!!
Мэи с заставкой в начале звучит грандиозно
Хорошо, нашли мы кратчайшее расстояние, а как узнать через какие точки? Из полученной таблицы я наглядно этого не увидел.
С этой таблицей я запутался еще сильнее
А для чего добавлять значение предыдущей метки?
Огромное спасибо! Ни как не мог найти ошибку в своей реализации алгоритма=)
Ничего не изменится, хоть 1000000! Можете еще алгоритмом Флойда воспользоваться, это еще проще, а потом свериться с Дейкстрой, все совпадет. Все эти алгоритмы доказываются, это только я так по-простому все рассказал... См. книги.
Отлично! Разобрался с алгоритмом Дейсктры!
Нет ли у Вас такого же доступного урока по алгоритмам Форда и Флойда? Не могу разобраться.
Заранее благодарен!!!
Мужик, спасиб большое
Надо внимательнее, видио-гид очень подробно расписан: шаг за шагом. Спасибо за алгоритм!
А как найти сам путь, а не только его длину?
Как вариант - при обновлении метки сохранять информацию о вершине-предшественнике.
Самое понятное разъяснение
Спасибо огромное!!!!!!!!!!!!!!
не могли бы пожалуйста, про D* еще рассказать
В рамках моей задачи, для поиска маршрута я могу использовать следующий подход - удалять из графа все длинные пути к одной и той-же вершине, оставляя только короткие. При вычислении веса вершины, если новый вес больше текущего, это значит, что найден дополнительный и более длинный путь к этой вершине. Следовательно этот путь (ребро) я могу удалить из графа. Для моей задачи это не критично. Таким образом в конце получаю граф в котором все точки связаны только одним маршрутом. Думаю это сработает.
Теперь я понимаю, почему в универе частенько ничего не понимал, этож надо, на 75% видео сказать, я ошибся в самом начале, давайте я за 2 секунды все переделаю.
Назначь длиной каждого ребра единицу, тогда этот алгоритм выведет тебе наименьшее кол-во рёбер от начальной до конечной вершины, а это и есть маршрут.
Спасибо автору
у нас в универе никогда не говорили "снести"
Будет и Форд-Флойд. А Форд-Фалкерсон уже есть. Ищите.
См, например, мою книгу "Графы в Maple"
Всё отлично понятно, спасибо за видео)
Спасибо большое!
Спасибо за ролик в любом случае. но мне кажется надо это понимать на языке символов и алгоритмов. так для общего частного понимания средних к коим и себя отношу умов
имеем 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]
Здравствуйте,этот алгоритм с первого раза приведет к кратчайшему пути?
Просто я для интереса выбрала не самый короткий путь на некоторых шагах а в итоге прошла более коротким путем чем если бы я действовала по алгоритму
Не может этого быть! Ошиблись.
@@Kirsanov2011 да,ошибка была в сносе,а где обзор на алгоритм Форда-Беллмана?
Могли бы вы рассказать о методе Беллмана-Мура? Для отрицательных весов
Зачем блок-схема? Могу и саму программу на простом и понятном языке Maple. См. стр. 111 моей книги "Графы в Maple" (книга есть в сети, но уже нет в продаже). Но там задействованы и спец.команды Maple, хотя их назначение довольно ясно...
Представленный алгоритм неполный, путь по вершинам, образующим минимальное расстояние не фиксируется. И вообще, объяснение не Дейкстры, родной алгоритм предусматривает обход по всем соседним вершинам, на которых еще не был. Далее Обход соседей от соседних вершин и т.д. ...
Спасибо!
спасибо огромное, у меня завтра экзамен по теории алгоритмов, надеюсь сдам)
Есть еще А*
Спасибо, все понятно. Но у нам в университете используют алгоритм из 6-ти ходов... То еще занятие, но результат тот же значит?
Здравствуйте. А алгоритм флойда уошера у вас нет? Я ваши видео глянул но ничего такого не встретил. Заранее спасибо
Спасибо!!!
просто мне именно блок-схема нужна для курсовой работы
все объяснение ваше понял, а вот как нарисовать блок-схему не понимаю(
я не понял как он с вершины 3 в вершину 2 попал ?
+Дмитрий Вихарев , снес "2" с предыдущей строки так как она весит (мы её не прошли), и сравнил - минимальное в получившейся строчке
А что делать если в ряду 2 одинаковые вершины?Решать относительно каждой?
Выбирать любую из них.
Спасибо, но я просто пытался вспомнить алгоритм.
Википедия расставила все на своим места
Безусловно плюс за ваш труд, но, как мне кажется, не помешало бы сделать метку на видео когда начинается сам алгоритм :)
да это же элементарно! как можно запутаться?
Вопрос такой. Если в одном ряду получилось два одинаковых числа и они оба наименьшие, то что делать?
Решение бывает не единственным. Поэтому берите любую. Потом для интереса возьмите другую.
Спасибо большое, все понятно)
Я извиняюсь, просто посмотрел описание на Вики, и уж очень странным оно мне показалось. Под впечатлением, отправил сообщение не по адресу. Прошу извинить.
Я только одного момента не понял, алгоритм Дейкстры находит именно ВЕЛИЧИНУ пути, в вашем примере, это 5, либо он может найти сам путь, т.е. перечень всех узлов по порядку которые нужно посетить?
Находим минимальный путь, а если нужен максимальный путь выбираем на каждом шаге максимум? Спасибо
+Марина иванова Минимум функции f(x) совпадает с максимумом A-f(x) - просто перевернуть график
Можете подробней описать, как найти максимальний путь?
1. Берете какое-нибудь большое число А, большее, чем вес любой дуги графа.
2. Все веса f_k графа заменяете на A-f_k
3. В полученном графе находите минимальный путь. Для исходного графа он будет максимальным.
Благодарю за ответ!
Спасибо.
Сделал лабу четверти группы, спасибо)
спасибо!
Спасибо за видео, всё понятно, но у меня вопрос, что делать если в конце 2 повторяется постоянная вершина 4 ?
Не совсем ясен вопрос. Постоянная вершина только один раз появляется. Потом ход на нее запрещен.
у меня повторяется наименьшее число
Если два одинаковых наименьших числа - берите любое.
Kirsanov2011 ясно, спасибо вам
@@Kirsanov2011 а что делать, если я пришла к определенной вершине (до конечной еще не дошла), но из нее ходы только в постоянные вершины, т.е. тупик?
Могли бы вы нарисовать блок схему к вашему решению и к алгоритму в целом??
Очень нужно!
Заранее спасибо!
Спасибо)
супер!
спасибо
superb! spassibo!
Ясно, алгоритм находит кратчайшее расстояние от одной вершины к остальным, а как быть если мне надо узнать не численное расстояние до остальных вершин, а маршрут (то есть список вершин чтобы в сумме удовлетворяли расстоянию) ?
Жалко, лектор этого не рассказал. Там нужно завести ещё один столбец, в котором указывать номер вершины, получившей постоянную пометку на данном шаге. С помощью этого столбца легко восстанавливается кратчайший путь до любой вершины. Также можно построить т.н. дерево кратчайших путей.
Или хотя бы понятный алгоритм написать, по которому можно будет нарисовать блок-схему
Как найти максимальный путь
выбирай найбольшее значение в каждой строке.
ок, буду дорабатывать. Спасибо.
Не понимаю, в вики описание отличается.
в вики графически представлено и псевдокодом
там тоже хорошая подача материала
Ааа зачем алгоритм дейскры если крускала быстрее
Алгоритм построения минимального остова? Зачем? или у Крускала есть еще алгоритм, который я не знаю?
чтобы дойти до вершины 6
и кстати за сколько работает алгоритм дейкстры
за квадрат или линию на логарифм
1) Алгоритм Крускала используется для построения минимального остова, а не для поиска кратчайших путей в орграфах.
2) Чтобы говорить об асимптотике алгоритма Дейкстры, нужно определиться со структурами данных, которые Вы собираетесь использовать.
В самой наивной реализации, если Вы будите хранить граф в виде матрицы смежности, то алгоритм будет работать за O(n^2), где n - число вершин графа. В самом деле, вам нужно будет сделать n шагов, на каждом из которых просматривать n вершин.
Вообще то это и так видно что кратчайшее расстояние 5 данный зачем формализм?
а если там тысячи вершин?
ничего не понял
слабо что-то понял, почему 5 если минимальное расстояние 1-3-6?
5 - это минимальное расстояние (минимальная сумма длин ребер), а не номер вершины, т.е длина ребра (1)->(3) = 1; длина ребра (3) -> (6) = 4. итого минимальное расстояние (1)->(3)->(6) = 1+4 = 5
4.5 < 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
Мне эта инф знакома. Скоро будет новый вариант видео "Модификация алг Дейкстры".