Алгоритм Дейкстры, решение задачи о кратчайшем пути
HTML-код
- Опубликовано: 5 фев 2025
- Не всегда можно решить задачу о кратчайшем пути Поиском решений Excel. Например, вершин у графа так много, что область изменяемых ячеек превышает допустимое их количество! В такой ситуации на помощь приходят специализированные алгоритмы. В нашем видеоуроке мы рассмотрим известный алгоритм Дейкстры и его практическое использование при решении задачи о кратчайшем пути.
Файл Excel с примером решения задачи вы можете скачать по ссылке:
drive.google.c...
Спасибо большое за Ваш труд. Просмотрела несколько видео с реализацией этого алгоритма, Ваше самое качественное. Очень наглядно и доходчиво объясняете.
Я согласна
Круто. Читаю книгу грокаем алгоритмы, там есть раздел по этому алгоритму, но после прочтения осталось много пробелов и это видео как раз таки все их заполнило
Спасибо, отлично объясняете.
Спасибо большое за объяснение, пока это лучшее что мне попадалось из видеоуроков. Особенно хочу отменить отличие от остальных видео других авторов - это упоминание постоянной и временной метки.
Спасибо. Несколько видео поглядел. Твое самое понятное.
и правда достойно объяснил, спасибо!!!
Доходчиво и пошагово, спасибо
Спасибо, отличное объяснение
Братанчик, спасибо, очень выручил
Спасибо большое! Все понятно :)
Ну хоть одно адекватное видео с объяснениями,спасибо .
благодарю
Заебс, просто царский лайк
Для неор.Графа все тоже самое, просматриваем инцидентные ребра?
подскажите, как поступать, когда на итерации L равен для для нескольких вершин.. какую вершину в этом случае принимать за постоянную?
Здравствуйте. Любую из них. Это не повлияет на конечный результат решения
@@StudyProf Оказалось, что влияет. На одном из шагов было несколько вершин с мин. значением, одна из них стала постоянной. А потом через несколько шагов оказалось, что есть путь короче, но вершина уже была постоянной и L для неё перезаписать не удалось.
откуда брали дуга 10 или 8? например 6.55 минут
из 1 вершины во 2 вес 10, а в 4 - вес 8, вес написан прямо над дугой
у вас есть видео решение транспортной задачи северо западным углом ,без поиска решений?
+Дмитрий такого на данный момент нет
+Дмитрий такого на данный момент нет
Здравствуйте! Вы не могли бы скинуть сам файл в формате .xlsx ?
Могу скинуть, скажите куда?
А давайте не много пообщаемся в скайпе, там и скинем? barhat099 буду признателен.
А как расписать все шаги алгоритма по всем вершинам?
Здравствуйте. Напишите мне на почту, что конкретно вам нужно marcellidenumana@gmail.com
почему на итерации 2, выбрали четвертую вершину? переход из 3 был только один
Здравствуйте. Спасибо за вопрос. На второй итерации мы сначала рассматриваем все смежные вершины с третьей вершиной. У третьей вершины такая вершина одна - это пятая вершина. Поэтому временная L для пятой вершины приняла значение 9. Далее работаем с вершинами, у которых метка L еще не приняла статус постоянной. Это вершины 2, 4, 5, 6, 7, 8, 9. Ищем ту, у которой временная метка L наименьшая. Это вершина 4. Поэтому у четвертой вершины метка L приняла статус постоянной.
Здравствуйте вы можете скинуть файл .xlsх ?
Здравствуйте. Прикрепил ссылку на файл Excel в описании к этому видео. Нажимайте на ссылку и скачивайте.
Транспортная задача математического программирования.
Чет хня какая-то(я про алгоритм), а это зацикливание на пункте 4 дает ли вообще какое-то преимущество чем простой перебор всех возможных путей и выбор кратчайшего пути?
точнее метод потенциалов