ИнтВиз

Дискретная математика · модуль 7 из 14

Алгоритм Дейкстры: как пакет находит маршрут

Узлы — дата-центры, на рёбрах задержка канала в миллисекундах. Алгоритм на каждом шаге берёт ближайший непосещённый узел и уточняет расстояния до его соседей.

  • кратчайший маршрут и посещённые узлы
  • текущий узел
  • отключённый канал

Теория

Взвешенный граф состоит из вершин и рёбер, каждому ребру приписан неотрицательный вес — длина, время или стоимость перехода. Граф удобно хранить матрицей смежности $W$: элемент $w_{ij}$ равен весу ребра между вершинами $i$ и $j$. У неориентированного графа матрица симметрична.

Алгоритм Дейкстры находит кратчайшие расстояния от начальной вершины $s$ до всех остальных:

  1. Расстояние до $s$ равно 0, до остальных вершин — $\infty$.
  2. Среди непосещённых вершин выбирается вершина $u$ с наименьшим расстоянием и помечается посещённой.
  3. Для каждого соседа $v$ выполняется релаксация: если путь через $u$ короче, расстояние обновляется:

$$ d(v) \leftarrow \min\bigl(d(v),\ d(u) + w(u, v)\bigr). $$

  1. Шаги 2–3 повторяются, пока остаются достижимые непосещённые вершины.

После посещения расстояние до вершины уже не меняется, поэтому алгоритм корректен только при неотрицательных весах. Маршрут восстанавливается по массиву предшественников: для каждой вершины запоминается, через какую вершину к ней пришли. Простая реализация работает за $O(V^2)$, реализация с двоичной кучей — за $O((V + E)\log V)$.

Где это применяется в IT

Протоколы маршрутизации OSPF и IS-IS запускают алгоритм Дейкстры на каждом маршрутизаторе. Тот же алгоритм прокладывает маршруты в навигаторах и логистике.

  • Вес ребра. Задержка, стоимость канала или расстояние. Отрицательных весов быть не должно.
  • Отказ канала. При обрыве канала маршрутизаторы пересчитывают пути, и трафик идёт в обход.
  • Производительность. С двоичной кучей (heapq в Python) сложность $O((V + E) \log V)$, что позволяет пересчитывать сети из тысяч узлов за миллисекунды.

Код на Python

Загружаю пример…