Скачать или смотреть Наглядное объяснение алгоритма кратчайшего пути Дейкстры | Как это работает | С примерами

Освойте алгоритм Дейкстры за 10 минут — наглядно просмотрите каждый шаг и научитесь использовать приоритетные очереди для поиска кратчайших путей в любом взвешенном графе.

Алгоритм Дейкстры — это проверенный метод для GPS-маршрутизации, оптимизации сетей и игрового ИИ.

В этом кратком уроке с анимацией вы узнаете:

→ Основы графов за 60 секунд: вершины, рёбра, веса
→ Как построить таблицу расстояний и приоритетную очередь
→ Пошаговое руководство по каждому обновлению релаксации
→ Что на самом деле делает «уменьшающий ключ» и почему кучи Фибоначчи могут ускорить процесс
→ Анализ временной и пространственной сложности для успешного прохождения следующего собеседования

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

Главы:
0:00 Введение – Пример графа
0:12 Построение таблицы отслеживания
0:36 Выбор начального узла
0:49 Заполнение очереди с приоритетами
1:01 Начало основного цикла
1:11 Посещение соседей узла A
2:36 Обработка узла b
3:09 Обновление E и C через узел B
3:40 Выбор E, ключ уменьшения
4:39 Что означает «ключ уменьшения»
8:32 Очередь опустела – алгоритм завершается
8:42 Обратный поиск кратчайшего пути A → C
9:17 Временная и пространственная сложность

Больше наглядных алгоритмов:
Кнута–Морриса–Пратта (КМП) – Сопоставление с образцом за O(n) →    • Knuth-Morris-Pratt Algorithm  
Поиск в глубину – Профессионально обходит любой граф →    • Depth First Search Visually Explained | DF...  
Графы 101 – Списки смежности и матрицы →    • Graphs Explained Visually | Data Structures  
Двоичные деревья поиска – Визуальная вставка, поиск и удаление →    • Binary Search Tree Visually Explained | Fu...  
Связанные списки – Указатели проще →    • Linked Lists Explained Visually  

Инструменты и информация
Manim (библиотека Python от 3Blue1Brown) для всех визуальных эффектов
Adobe Premiere Pro для редактирования
Музыка: «Sovereign» Кевина Маклеода (CC-BY 3.0) через Incompetech / Chosic

https://incompetech.com/
https://www.chosic.com/free-music/all/
https://creativecommons.org/licenses/...

#DijkstrasAlgorithm #ShortestPath #GraphTheory #DataStructures #AlgorithmVisualization #CodingInterview #Manim

Понравилось видео? Подпишитесь, чтобы получать еженедельные короткие анимации алгоритмов!