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