Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-02-26

1 Алгоритм Дейкстры - это алгоритм, который находит кратчайшие пути от одной заданной вершины до всех остальных вершин во взвешенном графе

2 Граф - это набор вершин и ребер. Вершины описывают объекты, ребра - связи между ними. У каждого ребра есть вес. Вес задает стоимость перехода: расстояние, время, цену, расход энергии. Алгоритм применим только тогда, когда все веса ребер неотрицательные. При отрицательных весах результат может быть неверным.

3 Алгоритм вычисляет не один маршрут "из A в B", а минимальные расстояния от источника ко всем достижимым вершинам. При сохранении предшественников можно восстановить сами пути.

4 <h2>Где используют алгоритм</h2>

5 Алгоритм подходит для задач, где систему удобно представить графом, а цель - минимизировать суммарную стоимость:

6 <ul><li>построение маршрутов на картах и в навигации;

7 </li>

8 <li>выбор оптимальных пересадок в транспортных сервисах;

9 </li>

10 <li>маршрутизация в сетях передачи данных;

11 </li>

12 <li>планирование движения роботов и автономных устройств;

13 </li>

14 <li>поиск пути и принятие решений в игровом ИИ;

15 </li>

16 <li>анализ потоков в инженерных моделях и схемах.

17 </li>

18 </ul>В каждом случае меняется смысл веса, но правило одно: суммируется стоимость пройденных ребер.

19 <h2>Как работает алгоритм</h2>

20 Алгоритм выполняется шаг за шагом. Он поддерживает текущие оценки расстояний от источника и постепенно "закрепляет" вершины с уже найденным минимальным расстоянием.

21 Состояния, которые используются в процессе:

22 <ul><li>метка расстояния для каждой вершины (лучшее найденное значение);

23 </li>

24 <li>признак обработанности вершины;

25 </li>

26 <li>при необходимости - массив предшественников для восстановления маршрута.

27 </li>

28 </ul><h2>Шаги выполнения</h2>

29 <ol><li>Инициализация

30 Источнику присваивается 0. Остальным вершинам присваивается бесконечность. Все вершины считаются необработанными.

31 </li>

32 <li>Выбор вершины

33 Среди необработанных выбирается вершина с минимальной меткой расстояния. Она становится текущей.

34 </li>

35 <li>Релаксация ребер

36 Для каждого соседа текущей вершины считается новая длина пути:

37 dist[current] + weight(current, neighbor)

38 Если новое значение меньше текущей метки соседа, метка обновляется. При восстановлении пути также обновляется предшественник.

39 </li>

40 <li>Фиксация

41 Текущая вершина помечается обработанной. Ее метка больше не изменяется.

42 Цикл повторяется, пока есть необработанные вершины с конечной меткой. Если вершина остается с бесконечностью, она недостижима из источника.

43 </li>

44 </ol><h2>Что получается на выходе</h2>

45 Результат работы - минимальные расстояния от источника:

46 <ul><li>до каждой достижимой вершины есть численное значение стоимости пути;

47 </li>

48 <li>при хранении предшественников можно восстановить конкретный маршрут.

49 </li>

50 </ul>Слово "расстояние" условное. В роли веса часто используют:

51 <ul><li>время прохождения;

52 </li>

53 <li>стоимость;

54 </li>

55 <li>задержку в сети;

56 </li>

57 <li>расход энергии;

58 </li>

59 <li>штраф или риск.

60 </li>

61 </ul><h2>Ограничения и важные условия</h2>

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