Как Работает Алгоритм Дейкстры [Spanning Tree]

Рет қаралды 20,541

Wilcodit

Күн бұрын

Пікірлер: 60

@АнтонСамойлов-л3ц 3 ай бұрын

Мне понравилось, всё чётко и ясно объяснено. Осталось сделать самостоятельную работу и запрограммировать дейкстру

@ЕвгенийСупремо 3 ай бұрын

Как по мне шляпа обьяснение

@rebrov_vyacheslav 3 ай бұрын

@@ЕвгенийСупремо что не понравилось?

@МаксимСебелев-х5я 3 ай бұрын

Анимация божественна и это не шутка

@skrupidonn 3 ай бұрын

украл с англ канала)

@Алексей-н1и9г 3 ай бұрын

Годная локализация, автору респект.

@firstmain52 2 ай бұрын

Очень милая анимация

@demidovmaxim1008 3 ай бұрын

Большое спасибо, это гениально

@testpu 3 ай бұрын

Очень доходчиво, спасибо

@EnergizerTheWhite 3 ай бұрын

Преступно мало просмотров и лайков! И подписчиков. Призывай подписаться в конце видео, это работает

@savvior3654 3 ай бұрын

Шикарное видео!

@belxsi 3 ай бұрын

Вот где ты был когда я информатику сдавал?

@MrSergioPalermo 3 ай бұрын

А - Ижевск С - Пермь Е -Екатеринбург D - Тюмень В - Курган G - Челябинск F - Уфа ))))))

@skatler5741 3 ай бұрын

Почему это видео не попалось мне раньше ? )

@JesseJames-mh5kb 3 ай бұрын

Кратчайший путь на вертолёте муахахаха))0)0)

@yeunborn Ай бұрын

привет, увидел твое видео насчёт олимпиадного программирования, хотел узнать, почему c# не подойдёт? он же вроде быстрый(не как плюсы, но уж в разы быстрее питона),у меня есть хорошая база на нем в ооп(промышленном программировании), думаю все же на нем писать всош, высшую пробу и т.д.😊

@tawerteam9804 3 ай бұрын

Топчик

@vadimnosurname 3 ай бұрын

Очень круто объяснил. Спасибо. Только 1 вопрос: если у нас получится такая ситуация, что расстояние от точки А до D составило бы 5. А расстояние от Е до В доставило бы 3. Тогда по этой задаче, мы бы точку D не проверили? Или мы бы сравнили полученное в итоге время в конечной точке с временем в не изученных городах?

@vadimnosurname 3 ай бұрын

Уже обсуждался этот вопрос) надо сравнивать время)

@iliaastafev5029 3 ай бұрын

Хм, непонятно. Давай чуть поменяем веса: CD = 2 а EB = 3. Тогда находясь в С мы имеем оценку для E = 4 а для D = 5 и идем в E. Но в реальности маршрут ACEB окажется длиннее чем ACDB. Получается нам нужно делать оценку всех возможных следующих вершин из всех предыдущих - а это в любом случае экспоненциальная сложность.

@АлександрТитов-в8щ 3 ай бұрын

Мне кажется, что вам необходимо алгоритм реализовать на бумажке, т.к. в голове тяжело одновременно удерживать большое кол-во переменных. Если вес граней изменить, то при проверке вершины "С" у вас "E" = 4, а "D" = 5. Вы проверите "Е" и увидите на вершине "B"=7, но вы не достигните конечного пункта. Т.к. на вершине "D" будет 5. И вам необходимо будет идти в вершину "D" и смотреть её пути. Вы увидите, что из "D" в "B" дорога будет занимать 6. И перезапишите. В оставшихся вариантах, у вас будет выбор идти в "B" или в "G", но в "G"=7, а в "B"=6. И вы достигните конечной вершины.

@iliaastafev5029 3 ай бұрын

@@АлександрТитов-в8щ ну то есть как я и говорю - полный перебор графа. Я даже если на очередном шаге при проверке следующих вершин нашел самую дешевую то мне все равно нужно будет зайти и во все остальные и сделать проверки там. Сложность остается экспоненциальной.

@wilcodit 3 ай бұрын

Пример c ACEB и ACDB: Когда мы пришли в Е, мы еще не нашли кратчайший маршрут в B. Кратчайший маршрут до вершины мы находим в тот момент, когда эта вершина становится самой ближайшей среди неиследованных. Нам не нужно делать оценку из всех во все. Чтобы разобраться, можно еще раз посмотреть как происходит обновление оценок) Если каким-то образом получилась экспоненциальная сложность вместо полиномиальной - это уже точно не Дейкстра^_^

@iliaastafev5029 3 ай бұрын

@@АлександрТитов-в8щ а я кстати понял. На 0:35 не совсем верно сформулирована задача возможно. Алгоритм Дейкстры не для того чтобы найти кратчайшее расстояние от А до Б, он для того чтобы найти кратчайшее расстояние от A до всех вершин.

@iliaastafev5029 3 ай бұрын

@@wilcodit ты прав - теоретически получается O(V+E). Если при программировании мы все поиски и обновления сделаем за O(1) например инициализировав граф в виде хэш-таблицы, то итоговая сложность останется и на практике около O(V+E).

@Djegur 3 ай бұрын

Оч круто

@-BezNika- 3 ай бұрын

Лайк паписка. Желаю больше просмотров

@vovanikotin 3 ай бұрын

Как работает А-Life?

@namibo 3 ай бұрын

Добрый, применял такой подход в своей игре. А ты можешь так же А Star алгоритм объяснить?)

@Andrey-vz1fe 3 ай бұрын

Если бы FB весил 3, то алгоритм пропустил бы оптимальный маршрут. Есть улучшенный алгоритм Дейкстры

@IronBruh 3 ай бұрын

Тут этот момент вроде учтен, потому как ранее определенный "неоптимальный" маршрут через ребро АС оказался оптимальным, т.е. произошла переоценка

@ЕвгенийСупремо 3 ай бұрын

Обьснение достаточно плохое потому что нужно не только анимацию делать, а еще и например показывать на примере отрезков выписанных растояние и тд. А в конце с графом и престановкой это вообще epic fail

@Leonard_Gray 3 ай бұрын

Это применяется в компьютерных играх для ИИ? Или где например? 🤔

@doctor_livsi_pod_phonk 3 ай бұрын

В интернете чекни, мега много где, если даже не прям на нем, то на версии его.

@Leonard_Gray 3 ай бұрын

Этот алгоритм универсален, поэтому его можно использовать в разных сферах. Например, в навигационных системах и картографии алгоритм Дейкстры может помочь проложить маршрут для пешеходов или автомобилей, избегая пробок и выбирая оптимальные дороги. В робототехнике этот алгоритм применяется для планирования движения роботов, чтобы они могли перемещаться в пространстве используя кратчайшие пути и обходя препятствия. В системах бронирования для поиска наиболее быстрых и дешевых билетов с учетом возможных пересадок. В компьютерных сетях алгоритм Дейкстры используется для определения оптимального маршрута передачи данных между узлами сети, минимизируя задержки и повышая эффективность передачи.

@Leonard_Gray 3 ай бұрын

Маршрутизаторы в этих ваших интернетах на нём основаны разве? 🤔

@doctor_livsi_pod_phonk 3 ай бұрын

@@Leonard_Gray я говорю загуглил, в этом плане я сказал...

@ЕвгенийСупремо 3 ай бұрын

Как по мне дучше чем остальные но обьяснение хромает

@priusfoxoriginal3061 3 ай бұрын

Вот вопрос, если бы, например cd было бы меньше чем ce,но bd было бы большим,то вроде как алгоритм не нашел кратчайшего пути

@Арт-ч2д 3 ай бұрын

Дело в том, что алгоритм выбирает точку с наименьшим значением среди ВСЕХ неисследованных, и если эта точка и является конечной, то алгоритм останавливается, так как другие пути гарантированно длиннее (ведь путь к одной из ПРОМЕЖУТОЧНЫХ точек другого маршрута дольше, чем весь путь от начальной к конечной) . Например, будь, CD=0,5 и весь путь к D равнялся бы 3,5. Пусть даже BD=3, и тогда значение в точке B было бы равно 7,5 на этой итерации (если было бы больше или равно 8, то путь не установился, так как путь A-F-B был бы короче). Однако, в таком случае алгоритм не остановился бы, так как оставалась бы неисследованная точка E, значение в которой равно 4 (что меньше 7,5 в точке B и в других точках). Снова бы произошло "раскрытие" данного пути, и значение в точке B стало бы равно 6, что меньше любой другой неисследованной точки и, так как эта точка является конечной, гарантировалось бы, что данный путь кратчайший.

@ankofl 3 ай бұрын

Да, но это не было оговорено в ролике, и с другими значениями ребер алгоритм работал бы неверно

@plotoh5087 3 ай бұрын

@@ankoflвсе оговорено, по этому алгоритму на подобном примере все легко совершается. при условии что расстояние не меньше 0

@anonsd5521 3 ай бұрын

Как по мне слишком затратный алгоритм, гораздо оптимальнее будет просто аннигилировать связи вершины, а связи везде суммировать. Например между городами C и B находится город D, который можно аннигилировать и получить сумму его связей, значит путь от C до B будет 5. Затем мы убираем C, между которыми 3 и 5, получаем 8 от А до В, 4 от А до Е, и 4 от А до А, что мы исключаем ввиду образования круга. Дальше так продолжаем, пока не останутся все возможные варианты добраться от А до В исключительно в виде связей, без вершин.

@evgenii_orwell 3 ай бұрын

Метод аннигиляции можно также соблюсти - но это если точки не соединены с более чем двумя вершинам, иначе удаляя вершины - надо учесть, что мы не один путь описывает, а сразу все...

@wilcodit 3 ай бұрын

Легким движением руки получаем О(n^3), вместо О(m log n)

@anonsd5521 3 ай бұрын

@@wilcodit Если не трудно, откуда O(n^3)?

@wilcodit 3 ай бұрын

@@anonsd5521 Если хотим путь V -> T -> U заменить на ребро V -> U, то нужно перебирать вершины V, T, U

@anonsd5521 3 ай бұрын

@@wilcodit Хорошо, спасибо за пояснение.

@nihonam 3 ай бұрын

А как может ребро быть с отрицательным весом?

@Leonard_Gray 3 ай бұрын

Как воздушный шарик! ＼(＾▽＾)／ Он имеет самую обычную массу, но отрицательный вес.

@nihonam 3 ай бұрын

@@Leonard_Gray но ведь тут речь идёт о потраченном на дорогу времени. оно не может быть отрицательным

@wilcodit 3 ай бұрын

Можно такой пример представить: Вес ребра - это его стоимость, если вес положительный, нужно заплатить, проходя по ребру, а если отрицательный, наоборот, получить деньги

@Leonard_Gray 3 ай бұрын

Представьте себе, отрицательные значения люди представляли себе не всегда, как и ноль! ... Не знаю, к чему я это сказал. Просто любопытно это всё.

@МихаилПапурин 3 ай бұрын

@@wilcodit С отрицательными весами тоже можно - добавится один проход по всему графу с запоминанием наименьшего отрицательного веса. И при учете ребра - из веса ребра вычитаем это значение.