Алгоритм Дейксты - это весьма элегантный способ нахождения кратчайшего пути сквозь любою сеть с возможностью задавать конкретный вес для каждой из дуг.
Это, пожалуй, лучшее видео по алгоритму Дейкстры. Чтобы объяснить сложные вещи так просто и понятно - это самому нужно прекрасно разбираться в вопросе. Спасибо, за лекцию! Вы супер!
Большое спасибо за видео. Наконец то я понял! Мало того, смог реализовать на С++ и оно заработало! Хочу добавить, что для обхода графа "в ширину" стоит использовать структуру данных "очередь", а для обхода графа "в глубину" стоит использовать структуру данных "стек".
Большое спасибо! Все очень понятно. Но небольшое замечание, не сочтите за дерзость. Я в первый раз смотрел с телефона и не все видел (т.к слишком маленькая "доска"), но с компа все ок)
Володя привет! Есть небольшая ошибка: точки А, В, С - между ними нужно изменить расстояние (например одну двойку заменить на 4 или 5), иначе не соблюдается правило треугольника. А так все очень классно у тебя на канале. Успехов в развитии.
Офигеть вы рассказали практически принцип маршрутизации очень доступным и понятным языком, очень хотелось бы еще урок ну примерно на практике , допустим под консоль с трассировкой и как там на самом деле все устроено, здесь стоят цифры мы циклом все опрашиваем и где у нас min оттуда и двигаемся, т .е. например дойти трафику до яндекса по России а не через америку, но как там выбирается что там за место той цифры которая по графам характеризует петлю, какие реальные параметры...
Буду честен, я не знаю как в реальности происходит маршрутизация в Интернет. То есть знаю теорию, но не практику. Вообще наверно было-бы интересно разобраться в этом, и тогда может быть записать такое видео занятие, как вы описали.
8:19 а вот если от C будет дуга в какую-нибудь "нижнюю" вершину, скажем, G, и вес у этой дуги будет маленький, как следствие, мы туда пойдём. Но если G больше не имеет дуг, т.е. просто лист, что тогда? Нам как-то придётся вернуться из той вершины, через которую мы туда попали (C). Задачу можно усложнить, добавив к G дугу в новую вершину H, из которой нет дуг (теперь она - лист). Как с этим справляться?
Спасибо за видео! Скажите пожалуйста, а нет ли у вас идей как можно было бы решитъ такую задачу?Может бытъ способ или примерный алгоритм? Она у нас была на олимпиаде по программированию, но разбора решения не было, правда сказали что можно делатъ разными способами, исполъзуя алгоритм Дейкстры, метод градиентного спуска, золотого сечения и др., но конкретного решения нам не сказали. Вот условие: "Дано N городов и M дорог соединяющих города(длина дорог известна). Также есть несколько объектов, для каждого объекта задан пункт старта и постоянная скорость, с которой движется объект. Необходимо узнать минимальное время, через которое объекты могут встретиться в одной точке (точка встречи не обязательно должна быть в городе, может и посреди дороги)."
Спасибо! Замечательное видео! Есть один вопросик: а что говорит этот алгоритм, если на определенной итерации мы получили одинаковое значение? Мы продолжаем расчет этого пути или возвращаемся к предыдущему?
В этом случае алгоритм просто берёт первый, на который наткнулся. В конечном счёте находится всё равно самый короткий путь, но не все возможные самые короткие пути.
ВОЛОДЯ ЭТО ЖЕ ТРАНСПОРНАЯ ЗАДАЧА, МАТЕМАТИЧЕСККОГО ПРОГРАММИРОВАНИЯ.(Фильм "Игры разума" 5 скаров),изучи хорошо дискретную мататику + основы бинарных множеств. Ну в вринциве нормально, удачи.
Ну почему "дуга весом"? Нагляднее было бы говорить "длиной". Неважно, что имеем дело не обязательно с длиной (а с ценой, временем, etc), принцип тот же.