Хм, непонятно. Давай чуть поменяем веса: CD = 2 а EB = 3. Тогда находясь в С мы имеем оценку для E = 4 а для D = 5 и идем в E. Но в реальности маршрут ACEB окажется длиннее чем ACDB. Получается нам нужно делать оценку всех возможных следующих вершин из всех предыдущих - а это в любом случае экспоненциальная сложность.
Мне кажется, что вам необходимо алгоритм реализовать на бумажке, т.к. в голове тяжело одновременно удерживать большое кол-во переменных. Если вес граней изменить, то при проверке вершины "С" у вас "E" = 4, а "D" = 5. Вы проверите "Е" и увидите на вершине "B"=7, но вы не достигните конечного пункта. Т.к. на вершине "D" будет 5. И вам необходимо будет идти в вершину "D" и смотреть её пути. Вы увидите, что из "D" в "B" дорога будет занимать 6. И перезапишите. В оставшихся вариантах, у вас будет выбор идти в "B" или в "G", но в "G"=7, а в "B"=6. И вы достигните конечной вершины.
@@АлександрТитов-в8щ ну то есть как я и говорю - полный перебор графа. Я даже если на очередном шаге при проверке следующих вершин нашел самую дешевую то мне все равно нужно будет зайти и во все остальные и сделать проверки там. Сложность остается экспоненциальной.
Пример c ACEB и ACDB: Когда мы пришли в Е, мы еще не нашли кратчайший маршрут в B. Кратчайший маршрут до вершины мы находим в тот момент, когда эта вершина становится самой ближайшей среди неиследованных. Нам не нужно делать оценку из всех во все. Чтобы разобраться, можно еще раз посмотреть как происходит обновление оценок) Если каким-то образом получилась экспоненциальная сложность вместо полиномиальной - это уже точно не Дейкстра^_^
@@АлександрТитов-в8щ а я кстати понял. На 0:35 не совсем верно сформулирована задача возможно. Алгоритм Дейкстры не для того чтобы найти кратчайшее расстояние от А до Б, он для того чтобы найти кратчайшее расстояние от A до всех вершин.
@@wilcodit ты прав - теоретически получается O(V+E). Если при программировании мы все поиски и обновления сделаем за O(1) например инициализировав граф в виде хэш-таблицы, то итоговая сложность останется и на практике около O(V+E).
Очень круто объяснил. Спасибо. Только 1 вопрос: если у нас получится такая ситуация, что расстояние от точки А до D составило бы 5. А расстояние от Е до В доставило бы 3. Тогда по этой задаче, мы бы точку D не проверили? Или мы бы сравнили полученное в итоге время в конечной точке с временем в не изученных городах?
привет, увидел твое видео насчёт олимпиадного программирования, хотел узнать, почему c# не подойдёт? он же вроде быстрый(не как плюсы, но уж в разы быстрее питона),у меня есть хорошая база на нем в ооп(промышленном программировании), думаю все же на нем писать всош, высшую пробу и т.д.😊
Этот алгоритм универсален, поэтому его можно использовать в разных сферах. Например, в навигационных системах и картографии алгоритм Дейкстры может помочь проложить маршрут для пешеходов или автомобилей, избегая пробок и выбирая оптимальные дороги. В робототехнике этот алгоритм применяется для планирования движения роботов, чтобы они могли перемещаться в пространстве используя кратчайшие пути и обходя препятствия. В системах бронирования для поиска наиболее быстрых и дешевых билетов с учетом возможных пересадок. В компьютерных сетях алгоритм Дейкстры используется для определения оптимального маршрута передачи данных между узлами сети, минимизируя задержки и повышая эффективность передачи.
Обьснение достаточно плохое потому что нужно не только анимацию делать, а еще и например показывать на примере отрезков выписанных растояние и тд. А в конце с графом и престановкой это вообще epic fail
Дело в том, что алгоритм выбирает точку с наименьшим значением среди ВСЕХ неисследованных, и если эта точка и является конечной, то алгоритм останавливается, так как другие пути гарантированно длиннее (ведь путь к одной из ПРОМЕЖУТОЧНЫХ точек другого маршрута дольше, чем весь путь от начальной к конечной) . Например, будь, CD=0,5 и весь путь к D равнялся бы 3,5. Пусть даже BD=3, и тогда значение в точке B было бы равно 7,5 на этой итерации (если было бы больше или равно 8, то путь не установился, так как путь A-F-B был бы короче). Однако, в таком случае алгоритм не остановился бы, так как оставалась бы неисследованная точка E, значение в которой равно 4 (что меньше 7,5 в точке B и в других точках). Снова бы произошло "раскрытие" данного пути, и значение в точке B стало бы равно 6, что меньше любой другой неисследованной точки и, так как эта точка является конечной, гарантировалось бы, что данный путь кратчайший.
Как по мне слишком затратный алгоритм, гораздо оптимальнее будет просто аннигилировать связи вершины, а связи везде суммировать. Например между городами C и B находится город D, который можно аннигилировать и получить сумму его связей, значит путь от C до B будет 5. Затем мы убираем C, между которыми 3 и 5, получаем 8 от А до В, 4 от А до Е, и 4 от А до А, что мы исключаем ввиду образования круга. Дальше так продолжаем, пока не останутся все возможные варианты добраться от А до В исключительно в виде связей, без вершин.
Метод аннигиляции можно также соблюсти - но это если точки не соединены с более чем двумя вершинам, иначе удаляя вершины - надо учесть, что мы не один путь описывает, а сразу все...
Можно такой пример представить: Вес ребра - это его стоимость, если вес положительный, нужно заплатить, проходя по ребру, а если отрицательный, наоборот, получить деньги
@@wilcodit С отрицательными весами тоже можно - добавится один проход по всему графу с запоминанием наименьшего отрицательного веса. И при учете ребра - из веса ребра вычитаем это значение.
Мне понравилось, всё чётко и ясно объяснено. Осталось сделать самостоятельную работу и запрограммировать дейкстру
Как по мне шляпа обьяснение
@@ЕвгенийСупремо что не понравилось?
Анимация божественна и это не шутка
украл с англ канала)
Годная локализация, автору респект.
Большое спасибо, это гениально
Очень доходчиво, спасибо
Очень милая анимация
Преступно мало просмотров и лайков! И подписчиков. Призывай подписаться в конце видео, это работает
Шикарное видео!
Вот где ты был когда я информатику сдавал?
А - Ижевск С - Пермь Е -Екатеринбург D - Тюмень В - Курган G - Челябинск F - Уфа ))))))
Почему это видео не попалось мне раньше ? )
Топчик
Кратчайший путь на вертолёте муахахаха))0)0)
Хм, непонятно. Давай чуть поменяем веса: CD = 2 а EB = 3. Тогда находясь в С мы имеем оценку для E = 4 а для D = 5 и идем в E. Но в реальности маршрут ACEB окажется длиннее чем ACDB. Получается нам нужно делать оценку всех возможных следующих вершин из всех предыдущих - а это в любом случае экспоненциальная сложность.
Мне кажется, что вам необходимо алгоритм реализовать на бумажке, т.к. в голове тяжело одновременно удерживать большое кол-во переменных. Если вес граней изменить, то при проверке вершины "С" у вас "E" = 4, а "D" = 5. Вы проверите "Е" и увидите на вершине "B"=7, но вы не достигните конечного пункта. Т.к. на вершине "D" будет 5. И вам необходимо будет идти в вершину "D" и смотреть её пути. Вы увидите, что из "D" в "B" дорога будет занимать 6. И перезапишите. В оставшихся вариантах, у вас будет выбор идти в "B" или в "G", но в "G"=7, а в "B"=6. И вы достигните конечной вершины.
@@АлександрТитов-в8щ ну то есть как я и говорю - полный перебор графа. Я даже если на очередном шаге при проверке следующих вершин нашел самую дешевую то мне все равно нужно будет зайти и во все остальные и сделать проверки там. Сложность остается экспоненциальной.
Пример c ACEB и ACDB:
Когда мы пришли в Е, мы еще не нашли кратчайший маршрут в B. Кратчайший маршрут до вершины мы находим в тот момент, когда эта вершина становится самой ближайшей среди неиследованных.
Нам не нужно делать оценку из всех во все. Чтобы разобраться, можно еще раз посмотреть как происходит обновление оценок)
Если каким-то образом получилась экспоненциальная сложность вместо полиномиальной - это уже точно не Дейкстра^_^
@@АлександрТитов-в8щ а я кстати понял. На 0:35 не совсем верно сформулирована задача возможно. Алгоритм Дейкстры не для того чтобы найти кратчайшее расстояние от А до Б, он для того чтобы найти кратчайшее расстояние от A до всех вершин.
@@wilcodit ты прав - теоретически получается O(V+E). Если при программировании мы все поиски и обновления сделаем за O(1) например инициализировав граф в виде хэш-таблицы, то итоговая сложность останется и на практике около O(V+E).
Очень круто объяснил. Спасибо. Только 1 вопрос: если у нас получится такая ситуация, что расстояние от точки А до D составило бы 5. А расстояние от Е до В доставило бы 3. Тогда по этой задаче, мы бы точку D не проверили? Или мы бы сравнили полученное в итоге время в конечной точке с временем в не изученных городах?
Уже обсуждался этот вопрос) надо сравнивать время)
привет, увидел твое видео насчёт олимпиадного программирования, хотел узнать, почему c# не подойдёт? он же вроде быстрый(не как плюсы, но уж в разы быстрее питона),у меня есть хорошая база на нем в ооп(промышленном программировании), думаю все же на нем писать всош, высшую пробу и т.д.😊
Лайк паписка. Желаю больше просмотров
Оч круто
Добрый, применял такой подход в своей игре. А ты можешь так же А Star алгоритм объяснить?)
Как работает А-Life?
Если бы FB весил 3, то алгоритм пропустил бы оптимальный маршрут. Есть улучшенный алгоритм Дейкстры
Тут этот момент вроде учтен, потому как ранее определенный "неоптимальный" маршрут через ребро АС оказался оптимальным, т.е. произошла переоценка
Это применяется в компьютерных играх для ИИ?
Или где например? 🤔
В интернете чекни, мега много где, если даже не прям на нем, то на версии его.
Этот алгоритм универсален, поэтому его можно использовать в разных сферах.
Например, в навигационных системах и картографии алгоритм Дейкстры может помочь проложить маршрут для пешеходов или автомобилей, избегая пробок и выбирая оптимальные дороги.
В робототехнике этот алгоритм применяется для планирования движения роботов, чтобы они могли перемещаться в пространстве используя кратчайшие пути и обходя препятствия.
В системах бронирования для поиска наиболее быстрых и дешевых билетов с учетом возможных пересадок.
В компьютерных сетях алгоритм Дейкстры используется для определения оптимального маршрута передачи данных между узлами сети, минимизируя задержки и повышая эффективность передачи.
Маршрутизаторы в этих ваших интернетах на нём основаны разве? 🤔
@@Leonard_Gray я говорю загуглил, в этом плане я сказал...
Обьснение достаточно плохое потому что нужно не только анимацию делать, а еще и например показывать на примере отрезков выписанных растояние и тд. А в конце с графом и престановкой это вообще epic fail
Как по мне дучше чем остальные но обьяснение хромает
Вот вопрос, если бы, например cd было бы меньше чем ce,но bd было бы большим,то вроде как алгоритм не нашел кратчайшего пути
Дело в том, что алгоритм выбирает точку с наименьшим значением среди ВСЕХ неисследованных, и если эта точка и является конечной, то алгоритм останавливается, так как другие пути гарантированно длиннее (ведь путь к одной из ПРОМЕЖУТОЧНЫХ точек другого маршрута дольше, чем весь путь от начальной к конечной) .
Например, будь, CD=0,5 и весь путь к D равнялся бы 3,5. Пусть даже BD=3, и тогда значение в точке B было бы равно 7,5 на этой итерации (если было бы больше или равно 8, то путь не установился, так как путь A-F-B был бы короче).
Однако, в таком случае алгоритм не остановился бы, так как оставалась бы неисследованная точка E, значение в которой равно 4 (что меньше 7,5 в точке B и в других точках). Снова бы произошло "раскрытие" данного пути, и значение в точке B стало бы равно 6, что меньше любой другой неисследованной точки и, так как эта точка является конечной, гарантировалось бы, что данный путь кратчайший.
Да, но это не было оговорено в ролике, и с другими значениями ребер алгоритм работал бы неверно
@@ankoflвсе оговорено, по этому алгоритму на подобном примере все легко совершается. при условии что расстояние не меньше 0
Как по мне слишком затратный алгоритм, гораздо оптимальнее будет просто аннигилировать связи вершины, а связи везде суммировать. Например между городами C и B находится город D, который можно аннигилировать и получить сумму его связей, значит путь от C до B будет 5. Затем мы убираем C, между которыми 3 и 5, получаем 8 от А до В, 4 от А до Е, и 4 от А до А, что мы исключаем ввиду образования круга. Дальше так продолжаем, пока не останутся все возможные варианты добраться от А до В исключительно в виде связей, без вершин.
Метод аннигиляции можно также соблюсти - но это если точки не соединены с более чем двумя вершинам, иначе удаляя вершины - надо учесть, что мы не один путь описывает, а сразу все...
Легким движением руки получаем О(n^3), вместо О(m log n)
@@wilcodit Если не трудно, откуда O(n^3)?
@@anonsd5521 Если хотим путь V -> T -> U заменить на ребро V -> U, то нужно перебирать вершины V, T, U
@@wilcodit Хорошо, спасибо за пояснение.
А как может ребро быть с отрицательным весом?
Как воздушный шарик! ＼(＾▽＾)／
Он имеет самую обычную массу, но отрицательный вес.
@@Leonard_Gray но ведь тут речь идёт о потраченном на дорогу времени. оно не может быть отрицательным
Можно такой пример представить:
Вес ребра - это его стоимость, если вес положительный, нужно заплатить, проходя по ребру, а если отрицательный, наоборот, получить деньги
Представьте себе, отрицательные значения люди представляли себе не всегда, как и ноль!
... Не знаю, к чему я это сказал. Просто любопытно это всё.
@@wilcodit С отрицательными весами тоже можно - добавится один проход по всему графу с запоминанием наименьшего отрицательного веса. И при учете ребра - из веса ребра вычитаем это значение.