Благодарю. Прохожу раздел динамического программирования, но очень понадобились знания о поиске кратчайшего пути в графе. Очень понятное и наглядное объяснение
Комментарий про понятность, приведённый ниже, кажется странным :) Всё очень понятно, Роман спасибо за материал. Я больше времени потратил на поиск нормального пояснения, нежели на осмысление ))
Боже, все жалуются, но ведь ролик предельно понятный! Вместо того, чтобы подумать минуту бегут писать об ошибках в ролике или вообще пишут скучно, жесть. Автору спасибо, наконец понял данный алгорит!
@@romantsarev1145 Рома, вопрос немного абстрактный - многие алгоритмы ст очки зрения имплементации на C# даются мне легко, а некоторые - как Дейкстра например, затыкаюсь в каком то моменте, теряю связь, нить и т.д. Этот ступор был у меня на некоторых собесах. Как выявить в себе причину тормоза? Буду крайне признателен за совет. Спасибо
Не должен. На 7:07 алгоритм закончил работу, и мы имеем кратчайшие пути от первой вершины до всех остальных вершин. На третьей итерации D5, равное 60, было минимальным [а, вообще говоря, единственным рассматреваемым] значением. Это значение и стало минимальным кратчайшим путем от вершины 1 до вершины 5, т.е. D5. Это то, что касается алгоритма Дейкстры. Если же просто посмотреть на граф, то можно заметить, что несмотря на то, что есть путь длины 70 (1->2->3->5), есть путь и короче 1->4->3->5, длина которого 60. (Собственно, это и есть то самое значение D5 = 60, полученное алгоритмом Дейкстры).
Не могли бы Вы пояснить, почему сложность здесь O(|E| * log|V|)? Кажется, алгоритм выполняет до |V| - 1 итераций и на каждой перебирает все доступные ребра. Похоже на O(|V| * |E|).
Общее представление дает, но сказать, что полностью понятно не могу. Название переменных из одной буквы - это мрак. Очень сильно путаешься, когда видишь p, i, d и т.п. Намного проще на простых примерах с осознанными названиями переменных.
Ооо я тут подумал, так это же по сути.. как и в мозгу работает, т.е. чем чаще каналик между 2мя вершинами контачит, (можно сделать в коде) тем больше вес т.е. значение этого ребра, а значит и т.е. тем лучше контакт между этими двумя "вершинами"//// 'эээ а ну да стоп, это же и есть нейросети..
G - граф, т.е. совокупность двух непересекающихся множеств: множества вершин V и множества ребер E. D - множество, которое мы формируем в ходе работы алгоритма. Подпробнее об этом в ролике.
Моим студентам понятно, когда я им читаю. Не знаю, почему Вам не зашел. У меня есть предложение. Раз уж Вы оцениваете, то, видимо, в алгоритме разобрались. Изложите ниже в двух словах. Как для себя. Человек наткнется на Ваш комментарий и сможет ознакомиться с алгоритмом в более лаконичной и простой форме.
@@romantsarev1145 я сам преподаю и с этим алгоритм реализовал не один app., просто студенти мои пришли и спросили как можно просто понять сложнейший алгоритм Дейкстры, на вопрос почему сложнейший кинули ваши видео. Можно быть хорошим специалистом но запутать все когда преподаете другим
А это случаем не электронный учебно-методический комплекс по дисциплине "Структуры и алгоритмы обработки данных" в БГУИРе, автором которой является Серебряная Л. В.
Нет, это алгоритм из УМКД "Структуры и алгоритмы обработки данных", автором которого является Царев Роман Юрьевич. На сегодняшний день этот УМКД представлен в виде электронного образовательного курса "Алгоритмы и структуры данных", автор все тот же. Что же касается самого алгоритма, то его автор, естественно, Дейкстра. Кстати, вот, в каком виде он опубликовал свой алгоритм: www-m3.ma.tum.de/foswiki/pub/MN0506/WebHome/dijkstra.pdf Думаю, что Дейкстра был бы не против того, что я рассказываю про его алгоритм.
Имеется ли у Вас опыт составления графа атак в АС с использованием этого алгоритма? Если да, то что Вы использовали в качестве стоимости (веса) в таком графе? Вероятность атаки от одного хоста (софта) к другому в компьютерной сети или что-то иное?
@@human_dasein эээ, да, куда мне до человека, который при просмотре образовательного видева единственное, что смог из себя вытянуть, это какую-то кринжовую шутку с референсом на кал для блаженных.
Нет, так кажется всем (я надеюсь). Однако, это очень странный вопрос. В видео ничего не говорится о том, что существует путь 1,2,4,3,5. Ну, потому что его нет. Полагаю, что речь идет об особых путях. Рекомендую пересмотреть, как они расчитываются на каждой итерации: 2:27-4:13 Перед этим будет полезно вспомнить, что такое особый путь, что такое множество S и массив D: 0:35-1:31 После просмотра Вы получите ответ на Ваш вопрос, тот, что между строк.
Да, из 2 в 4 нет пути. Все получилось. Сейчас дам наводку. Полагаю, что речь идет об особых путях. Рекомендую пересмотреть, как они расчитываются на каждой итерации: 2:27-4:13 Перед этим будет полезно вспомнить, что такое особый путь, что такое множество S и массив D: 0:35-1:31 После просмотра у Вас должен отпасть вопрос о пути между вершинами 2 и 4.
@@romantsarev1145 проблема в том, братец, что ты своим контентом засоряешь ютюб и найти нормальный материал от адекватных опытных программистов становится сложнее. И это осложняет жизнь таким как я, потому я и высказываю тебе свое негодование твоим контентом, т.е. обоснованно и правомерно.
Идеальный вариант для оформления Контрольных и Лабораторных работ по Дискретной математике. Спасибо, сдал на "отлично".
Всё чётко и по делу. Алгоритм стал понятен после 1 просмотра.
Спасибо, рад что заходит!
Спасибо Вам за объяснение! Смог понять как же работает алгоритм Дейкстры
Блииин, так круто)) Спасибо большое, теперь имею хотя бы общее представление об этом алгоритме, очень помогли ❤️❤️❤️❤️❤️
Рад, что понравилось
Лучшее объяснение этого алгоритма во всём ютубе. Лайк и подписка.
Благодарю
muchas gracias!
Люблю когда пытаются охватить максимальное количество представлений информации. Спасибо)
Пожалуйста
Впервые программный код мне понятнее самого объяснения. Но надо отдать должное - представленная таблица очень наглядно показывает, что откуда берётся.
Благодарю. Прохожу раздел динамического программирования, но очень понадобились знания о поиске кратчайшего пути в графе. Очень понятное и наглядное объяснение
Пожалуйста. Рад, что пригодилось
Комментарий про понятность, приведённый ниже, кажется странным :) Всё очень понятно, Роман спасибо за материал. Я больше времени потратил на поиск нормального пояснения, нежели на осмысление ))
Пожалуйста
Спасибо, как раз то что надо... мне как раз в игре надо было по way point-ам найти оптимальный путь =)
Спасибо большое! Благодаря вам я поняла этот алгоритм! :)
Пожалуйста
Огромное спасибо!
Пожалуйста
Боже, все жалуются, но ведь ролик предельно понятный! Вместо того, чтобы подумать минуту бегут писать об ошибках в ролике или вообще пишут скучно, жесть. Автору спасибо, наконец понял данный алгорит!
Благодарю за отзыв!
thanks
You are welcome
@@romantsarev1145 Рома, вопрос немного абстрактный - многие алгоритмы ст очки зрения имплементации на C# даются мне легко, а некоторые - как Дейкстра например, затыкаюсь в каком то моменте, теряю связь, нить и т.д. Этот ступор был у меня на некоторых собесах. Как выявить в себе причину тормоза? Буду крайне признателен за совет. Спасибо
Спасибо, это очень помогло
Пожалуйста!
Спасибо за объяснение
Пожалуйста
хорош!
Мерси
👍
Вроде в таблице (7:07) в D5 кратчайший путь должен быть 70, а не 60
Не должен. На 7:07 алгоритм закончил работу, и мы имеем кратчайшие пути от первой вершины до всех остальных вершин. На третьей итерации D5, равное 60, было минимальным [а, вообще говоря, единственным рассматреваемым] значением. Это значение и стало минимальным кратчайшим путем от вершины 1 до вершины 5, т.е. D5. Это то, что касается алгоритма Дейкстры.
Если же просто посмотреть на граф, то можно заметить, что несмотря на то, что есть путь длины 70 (1->2->3->5), есть путь и короче 1->4->3->5, длина которого 60. (Собственно, это и есть то самое значение D5 = 60, полученное алгоритмом Дейкстры).
Roman Tsarev понял, спасибо большое
Не могли бы Вы пояснить, почему сложность здесь O(|E| * log|V|)? Кажется, алгоритм выполняет до |V| - 1 итераций и на каждой перебирает все доступные ребра. Похоже на O(|V| * |E|).
Общее представление дает, но сказать, что полностью понятно не могу. Название переменных из одной буквы - это мрак. Очень сильно путаешься, когда видишь p, i, d и т.п. Намного проще на простых примерах с осознанными названиями переменных.
А бывают и обратные рекомендации. Мол, зачем писать number_of_item, нельзя что ли просто i написать?!
@@romantsarev1145 Дядюшка Боб авторитетнее случайных комментаторов)
Ооо я тут подумал, так это же по сути.. как и в мозгу работает, т.е. чем чаще каналик между 2мя вершинами контачит, (можно сделать в коде) тем больше вес т.е. значение этого ребра, а значит и т.е. тем лучше контакт между этими двумя "вершинами"//// 'эээ а ну да стоп, это же и есть нейросети..
а откуда нам знать что такие буквы D,G,V,E и т.д ?Чего эти буквы означает и где они находится?или все это формула?
G - граф, т.е. совокупность двух непересекающихся множеств: множества вершин V и множества ребер E. D - множество, которое мы формируем в ходе работы алгоритма. Подпробнее об этом в ролике.
Спасибо огромное за видео, вполне понятно. Можно вопрос, а что делать если скажем D3 и D5 будут равны. 3 или 5 взять как следуюший w?
Все равно. Отмечу при этом, что они должны быть минимальны.
@@romantsarev1145 спасибо большое!
@@sargismkrtchyan9598 Пожалуйста
Как можно простейший алгоритм объяснить так сложно и запутанно.
Моим студентам понятно, когда я им читаю. Не знаю, почему Вам не зашел.
У меня есть предложение. Раз уж Вы оцениваете, то, видимо, в алгоритме разобрались. Изложите ниже в двух словах. Как для себя. Человек наткнется на Ваш комментарий и сможет ознакомиться с алгоритмом в более лаконичной и простой форме.
@@romantsarev1145 я сам преподаю и с этим алгоритм реализовал не один app., просто студенти мои пришли и спросили как можно просто понять сложнейший алгоритм Дейкстры, на вопрос почему сложнейший кинули ваши видео. Можно быть хорошим специалистом но запутать все когда преподаете другим
Такое впечатление, что просто сухо читается методичка.
Но нет
Обидно, что под всякими тупостями так много лайков, а такое полезное видео всего 1,4к лайков
Спасибо. Очень приятно!
А это случаем не электронный учебно-методический комплекс по дисциплине
"Структуры и алгоритмы обработки данных" в БГУИРе, автором которой является Серебряная Л. В.
Нет, это алгоритм из УМКД "Структуры и алгоритмы обработки данных", автором которого является Царев Роман Юрьевич. На сегодняшний день этот УМКД представлен в виде электронного образовательного курса "Алгоритмы и структуры данных", автор все тот же. Что же касается самого алгоритма, то его автор, естественно, Дейкстра. Кстати, вот, в каком виде он опубликовал свой алгоритм: www-m3.ma.tum.de/foswiki/pub/MN0506/WebHome/dijkstra.pdf Думаю, что Дейкстра был бы не против того, что я рассказываю про его алгоритм.
Имеется ли у Вас опыт составления графа атак в АС с использованием этого алгоритма? Если да, то что Вы использовали в качестве стоимости (веса) в таком графе? Вероятность атаки от одного хоста (софта) к другому в компьютерной сети или что-то иное?
Задачу по атакам в АС решать не доводилось.
А нельзя сначала было объяснить по человечески, а потом с формулами?
Можно
Не понятно как на 1 шаге в D[5] получилось 100. D[2] == 10 + стоимость от 2 до 5 = 60, итого 70. Вроде как выбираем меньшее из 100 и 70, почему 100?
D[5]=min(100, 10+бесконечность). Выбираем между 100 и бесконечностью.
@@romantsarev1145 а почему там бесконечность? Потому что нет прямого пути к Д(5)?
@@joshua_we1t Да
А рисунок можно было сделать соответствующий указанным весам? А не правильный пятиугольник
Естественно
Не надо пиарить злодея из ведьмака 3
ахахах классно, братан, как всегда 🤣👍👍
@@llllNEOllllchannel ты только что выдал свой мленький возраст
@@human_dasein эээ, да, куда мне до человека, который при просмотре образовательного видева единственное, что смог из себя вытянуть, это какую-то кринжовую шутку с референсом на кал для блаженных.
@@llllNEOllllchannel так я никакую кринжовую шутку не писал, как раз таки одна из таких оставлена под моим комментарием каким-то инцелом.
@@human_dasein
-> Референс к ведьмаку 3
-> Пытается заовнить, называя другого инцелом
Мне одному кажется, что пути 1,2,4,3,5 _НЕТ_, так как нет прямого сообщения между 2 и 4?
Нет, так кажется всем (я надеюсь). Однако, это очень странный вопрос. В видео ничего не говорится о том, что существует путь 1,2,4,3,5. Ну, потому что его нет.
Полагаю, что речь идет об особых путях.
Рекомендую пересмотреть, как они расчитываются на каждой итерации: 2:27-4:13
Перед этим будет полезно вспомнить, что такое особый путь, что такое множество S и массив D: 0:35-1:31
После просмотра Вы получите ответ на Ваш вопрос, тот, что между строк.
Не понятно
Бывает...
от 2 на 4 нету же пути. Чет не понятно. И у вас же не получилось путь
Да, из 2 в 4 нет пути. Все получилось. Сейчас дам наводку.
Полагаю, что речь идет об особых путях.
Рекомендую пересмотреть, как они расчитываются на каждой итерации: 2:27-4:13
Перед этим будет полезно вспомнить, что такое особый путь, что такое множество S и массив D: 0:35-1:31
После просмотра у Вас должен отпасть вопрос о пути между вершинами 2 и 4.
Ничего не понятно
¯\_(ツ)_/¯
Псевдо код это уже как то слишком сложно для понимания.
Уж как мог. Можно погуглить сразу код на любом языке. Алгоритм более чем известный. Точно найдете код на любом языке.
Бездарно
Уж извините
"дуга", "источник"... ну ты даешь... фу
Не любо - не слушай.
Что касается терминологии, всё там верно.
@@romantsarev1145 проблема в том, братец, что ты своим контентом засоряешь ютюб и найти нормальный материал от адекватных опытных программистов становится сложнее. И это осложняет жизнь таким как я, потому я и высказываю тебе свое негодование твоим контентом, т.е. обоснованно и правомерно.