В институте я много слышал про конечные автоматы (КА), но это всё было теорией - как облака в небе: воды в них много, а напиться нельзя. Корпел три месяца после института, пока не реализовал свой КА в коде в 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, он как раз основан на методе Дейкстры. Посмотрел видео, разобрался. Спасибо)
Спасибо. А если так?! Найти все пути из первой точки в последнюю; затем для каждого найденного пути найти расстояние; сохранить все в массиве, отсортировать массив расстояний по возрастанию, то первое значение и будет кратчайшим путём. Это уже будет далеко от алгоритма Дейкстры?!
Отлично! Разобрался с алгоритмом Дейсктры! Нет ли у Вас такого же доступного урока по алгоритмам Форда и Флойда? Не могу разобраться. Заранее благодарен!!!
Ничего не изменится, хоть 1000000! Можете еще алгоритмом Флойда воспользоваться, это еще проще, а потом свериться с Дейкстрой, все совпадет. Все эти алгоритмы доказываются, это только я так по-простому все рассказал... См. книги.
Зачем блок-схема? Могу и саму программу на простом и понятном языке Maple. См. стр. 111 моей книги "Графы в Maple" (книга есть в сети, но уже нет в продаже). Но там задействованы и спец.команды Maple, хотя их назначение довольно ясно...
В рамках моей задачи, для поиска маршрута я могу использовать следующий подход - удалять из графа все длинные пути к одной и той-же вершине, оставляя только короткие. При вычислении веса вершины, если новый вес больше текущего, это значит, что найден дополнительный и более длинный путь к этой вершине. Следовательно этот путь (ребро) я могу удалить из графа. Для моей задачи это не критично. Таким образом в конце получаю граф в котором все точки связаны только одним маршрутом. Думаю это сработает.
Теперь я понимаю, почему в универе частенько ничего не понимал, этож надо, на 75% видео сказать, я ошибся в самом начале, давайте я за 2 секунды все переделаю.
Я извиняюсь, просто посмотрел описание на Вики, и уж очень странным оно мне показалось. Под впечатлением, отправил сообщение не по адресу. Прошу извинить. Я только одного момента не понял, алгоритм Дейкстры находит именно ВЕЛИЧИНУ пути, в вашем примере, это 5, либо он может найти сам путь, т.е. перечень всех узлов по порядку которые нужно посетить?
Здравствуйте,этот алгоритм с первого раза приведет к кратчайшему пути? Просто я для интереса выбрала не самый короткий путь на некоторых шагах а в итоге прошла более коротким путем чем если бы я действовала по алгоритму
Представленный алгоритм неполный, путь по вершинам, образующим минимальное расстояние не фиксируется. И вообще, объяснение не Дейкстры, родной алгоритм предусматривает обход по всем соседним вершинам, на которых еще не был. Далее Обход соседей от соседних вершин и т.д. ...
Спасибо за ролик в любом случае. но мне кажется надо это понимать на языке символов и алгоритмов. так для общего частного понимания средних к коим и себя отношу умов
имеем 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]
1. Берете какое-нибудь большое число А, большее, чем вес любой дуги графа. 2. Все веса f_k графа заменяете на A-f_k 3. В полученном графе находите минимальный путь. Для исходного графа он будет максимальным.
Ясно, алгоритм находит кратчайшее расстояние от одной вершины к остальным, а как быть если мне надо узнать не численное расстояние до остальных вершин, а маршрут (то есть список вершин чтобы в сумме удовлетворяли расстоянию) ?
Жалко, лектор этого не рассказал. Там нужно завести ещё один столбец, в котором указывать номер вершины, получившей постоянную пометку на данном шаге. С помощью этого столбца легко восстанавливается кратчайший путь до любой вершины. Также можно построить т.н. дерево кратчайших путей.
1) Алгоритм Крускала используется для построения минимального остова, а не для поиска кратчайших путей в орграфах. 2) Чтобы говорить об асимптотике алгоритма Дейкстры, нужно определиться со структурами данных, которые Вы собираетесь использовать. В самой наивной реализации, если Вы будите хранить граф в виде матрицы смежности, то алгоритм будет работать за O(n^2), где n - число вершин графа. В самом деле, вам нужно будет сделать n шагов, на каждом из которых просматривать n вершин.
5 - это минимальное расстояние (минимальная сумма длин ребер), а не номер вершины, т.е длина ребра (1)->(3) = 1; длина ребра (3) -> (6) = 4. итого минимальное расстояние (1)->(3)->(6) = 1+4 = 5
Большое спасибо. Это лучшее объяснение данного алгоритма, из тех что я встретил на просторах. Понятно и наглядно👍👍
Пасибо , что спасаете ленивых студентов..
Объяснение с прямой линией вижу в первый раз, и это очень удобно. Спасибо большое!
Вы сэкономили мне кучу времени. Спасибо!
Посмотрел куча других видео - ничего не понял. Посмотрел ваше - все понял с самого начала. Спасибо за доступное объяснение.
Спасибо Вам огромное! Наконец-то окончательно разобрался с этим алгоритмом.
В институте я много слышал про конечные автоматы (КА), но это всё было теорией - как облака в небе: воды в них много, а напиться нельзя. Корпел три месяца после института, пока не реализовал свой КА в коде в 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" или на Хабре: "Бублики и Коржики Программирования".
Вы просто лучший
Огромное спасибо! Вы помогли мне понять этот алгоритм!
Хочу заметить, что алгоритм физически напоминает поведение воды когда она накапливается на неровном ландшафте, первым делом заливает пустоты, затем если вокруг высокие препятствия - ищет следующий кратчайший путь повышая уровень воды. Повышение уровня воды - это аналог "удорожания маршрута".
Благодарю вас за информационный, легко усвоиемый видео урок.
спасибо, тятя, вы очинь умнний. Я сам узбек делал поступило ни унивирсэтет. очинь сложна(((. вы памоч спосибо
Благодаря вам , получил 90 баллов по дискретной математике. Спасибо!!!
спасибобольшое вам за очень простое обьяснение. здоровья и процветания вам
Для поиска последовательности узлов алгоритм надо еще немного доработать. Но не принципиально, просто на каждом этапе запоминать, из чего складывается минимальная сумма, а потом стирать ее, если найдется еще меньше (а в ней тоже уже хранится последовательность...). На любом алгоритм.языке это не трудно сделать. Я это делал в Maple (см. мою книгу "Графы в Maple", она есть в сети)
Пересмотрел несколько раз, поставил лайк, алгоритм запомнил, идеально
Никак не мог разобраться, как работает протокол динамической маршрутизации OSPF, он как раз основан на методе Дейкстры. Посмотрел видео, разобрался. Спасибо)
Спасибо огромное, уже столько времени прошло, а акутально и по сей день:)
Отлично! Очень доходчиво. Спасибо!
просмотрите еще раз и почитайте книги... Успехов!
Большое спасибо,вам за ваши труды
Спасибо. А если так?! Найти все пути из первой точки в последнюю; затем для каждого найденного пути найти расстояние; сохранить все в массиве, отсортировать массив расстояний по возрастанию, то первое значение и будет кратчайшим путём. Это уже будет далеко от алгоритма Дейкстры?!
Вот в том то и дело - как найти ВСЕ пути? Перебором? Думайте. Вопрос не закрыт. Алг Дейкстры - это одно из решений
@@Kirsanov2011вот такой у меня получился способ, (без кода) на основе упорядоченной матрицы: th-cam.com/video/FBk5vDdusoY/w-d-xo.html
Благодарю) Долго не мог понять, теперь разобрался)
Спасибо большое! Очень доходчиво объясняете.
благодаря видео я сдела свою контрольную работу по графам))) спасибо БОЛЬШОЕ
+Дима Рекун Ради этого я и трудился...
Спасибо большое вам за обьяснение!
Большое спасибо за доступное объяснение
Хорошо, нашли мы кратчайшее расстояние, а как узнать через какие точки? Из полученной таблицы я наглядно этого не увидел.
Спасибо, док.
Очень интересно и доходчиво, спасибо!
Спасибо, всех благ вам за ваши труды :)
Отличное представление!
Отлично! Разобрался с алгоритмом Дейсктры!
Нет ли у Вас такого же доступного урока по алгоритмам Форда и Флойда? Не могу разобраться.
Заранее благодарен!!!
Спасибо за урок..Всё ясно и понятно!!)нет ничего лишнего - всё по теме!!
Отличное видео, все очень понятно! Единственный вопрос, как вычислять сам путь (порядок вершин), а не только длину пути?
+Katty Rein Пишите каждый раз список предшествующих вершин
Спасибо Вам большое, очень доступно и понятно объяснили.
Отличное объяснение) Спасибо!!
Большое спасибо,все понятно и доступно
Спасибо большое, всё очень понятно!
Пока что самое понятное объяснение, которое я встречал в инете
Мэи с заставкой в начале звучит грандиозно
С этой таблицей я запутался еще сильнее
Могли бы вы рассказать о методе Беллмана-Мура? Для отрицательных весов
Мужик, спасиб большое
не могли бы пожалуйста, про D* еще рассказать
А как найти сам путь, а не только его длину?
Как вариант - при обновлении метки сохранять информацию о вершине-предшественнике.
Назначь длиной каждого ребра единицу, тогда этот алгоритм выведет тебе наименьшее кол-во рёбер от начальной до конечной вершины, а это и есть маршрут.
А для чего добавлять значение предыдущей метки?
Ничего не изменится, хоть 1000000! Можете еще алгоритмом Флойда воспользоваться, это еще проще, а потом свериться с Дейкстрой, все совпадет. Все эти алгоритмы доказываются, это только я так по-простому все рассказал... См. книги.
Огромное спасибо! Ни как не мог найти ошибку в своей реализации алгоритма=)
Надо внимательнее, видио-гид очень подробно расписан: шаг за шагом. Спасибо за алгоритм!
Зачем блок-схема? Могу и саму программу на простом и понятном языке Maple. См. стр. 111 моей книги "Графы в Maple" (книга есть в сети, но уже нет в продаже). Но там задействованы и спец.команды Maple, хотя их назначение довольно ясно...
Спасибо огромное!!!!!!!!!!!!!!
Будет и Форд-Флойд. А Форд-Фалкерсон уже есть. Ищите.
В рамках моей задачи, для поиска маршрута я могу использовать следующий подход - удалять из графа все длинные пути к одной и той-же вершине, оставляя только короткие. При вычислении веса вершины, если новый вес больше текущего, это значит, что найден дополнительный и более длинный путь к этой вершине. Следовательно этот путь (ребро) я могу удалить из графа. Для моей задачи это не критично. Таким образом в конце получаю граф в котором все точки связаны только одним маршрутом. Думаю это сработает.
Самое понятное разъяснение
Теперь я понимаю, почему в универе частенько ничего не понимал, этож надо, на 75% видео сказать, я ошибся в самом начале, давайте я за 2 секунды все переделаю.
Я извиняюсь, просто посмотрел описание на Вики, и уж очень странным оно мне показалось. Под впечатлением, отправил сообщение не по адресу. Прошу извинить.
Я только одного момента не понял, алгоритм Дейкстры находит именно ВЕЛИЧИНУ пути, в вашем примере, это 5, либо он может найти сам путь, т.е. перечень всех узлов по порядку которые нужно посетить?
Спасибо автору
Всё отлично понятно, спасибо за видео)
См, например, мою книгу "Графы в Maple"
Спасибо большое!
Здравствуйте,этот алгоритм с первого раза приведет к кратчайшему пути?
Просто я для интереса выбрала не самый короткий путь на некоторых шагах а в итоге прошла более коротким путем чем если бы я действовала по алгоритму
Не может этого быть! Ошиблись.
@@Kirsanov2011 да,ошибка была в сносе,а где обзор на алгоритм Форда-Беллмана?
у нас в универе никогда не говорили "снести"
Здравствуйте. А алгоритм флойда уошера у вас нет? Я ваши видео глянул но ничего такого не встретил. Заранее спасибо
Могли бы вы нарисовать блок схему к вашему решению и к алгоритму в целом??
Очень нужно!
Заранее спасибо!
Представленный алгоритм неполный, путь по вершинам, образующим минимальное расстояние не фиксируется. И вообще, объяснение не Дейкстры, родной алгоритм предусматривает обход по всем соседним вершинам, на которых еще не был. Далее Обход соседей от соседних вершин и т.д. ...
Спасибо!
спасибо огромное, у меня завтра экзамен по теории алгоритмов, надеюсь сдам)
Есть еще А*
Спасибо!!!
я не понял как он с вершины 3 в вершину 2 попал ?
+Дмитрий Вихарев , снес "2" с предыдущей строки так как она весит (мы её не прошли), и сравнил - минимальное в получившейся строчке
просто мне именно блок-схема нужна для курсовой работы
все объяснение ваше понял, а вот как нарисовать блок-схему не понимаю(
супер!
Спасибо, все понятно. Но у нам в университете используют алгоритм из 6-ти ходов... То еще занятие, но результат тот же значит?
Спасибо за ролик в любом случае. но мне кажется надо это понимать на языке символов и алгоритмов. так для общего частного понимания средних к коим и себя отношу умов
имеем 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. В полученном графе находите минимальный путь. Для исходного графа он будет максимальным.
Благодарю за ответ!
Вопрос такой. Если в одном ряду получилось два одинаковых числа и они оба наименьшие, то что делать?
Решение бывает не единственным. Поэтому берите любую. Потом для интереса возьмите другую.
А что делать если в ряду 2 одинаковые вершины?Решать относительно каждой?
Выбирать любую из них.
Безусловно плюс за ваш труд, но, как мне кажется, не помешало бы сделать метку на видео когда начинается сам алгоритм :)
Ясно, алгоритм находит кратчайшее расстояние от одной вершины к остальным, а как быть если мне надо узнать не численное расстояние до остальных вершин, а маршрут (то есть список вершин чтобы в сумме удовлетворяли расстоянию) ?
Жалко, лектор этого не рассказал. Там нужно завести ещё один столбец, в котором указывать номер вершины, получившей постоянную пометку на данном шаге. С помощью этого столбца легко восстанавливается кратчайший путь до любой вершины. Также можно построить т.н. дерево кратчайших путей.
Спасибо.
Спасибо за видео, всё понятно, но у меня вопрос, что делать если в конце 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
Мне эта инф знакома. Скоро будет новый вариант видео "Модификация алг Дейкстры".