Алгоритм Дейкстры
Алгоритм Дейкстры позволяет найти кратчайший путь между двумя любыми вершинами графа (или кратчайший путь сети между заданным исходным и любым другим узлом).
Граф — это совокупность двух множеств: точек (называются вершинами) и путей между ними (изображаются линиями и называются рёбрами).
Алгоритм Дейкстры применяется в жизни. Например, можно использовать графы для моделирования транспортной сети, где точки (вершины) являются объектами, которые отправляют или получают посылки/продукты (места, что водитель должен посетить), а рёбра (линии) представляют собой соединяющие их дороги:
Графы могут быть двух типов:
- направленный граф: если для каждой пары узлов можно сделать переход от одного узла к другому только в определённом направлении; для обозначения такого графа используются стрелки вместо простых линий (пример из жизни: когда на дороге есть только одностороннее движение);
- ненаправленный граф: если для каждой пары узлов можно сделать переход от одного к другому в обоих направлениях (пример из жизни: когда на дороге есть двустороннее движение).
Пример
Рассмотрим представленный выше пример:
Алгоритм произведёт кратчайший путь от узла 0 ко всем остальным узлам графа.
Для этого графа мы будем предполагать, что вес рёбер (вес или стоимость всегда являются неотрицательными, т.е. ≥ 0; это цифра возле каждой линии) представляет собой расстояние между двумя узлами:
Мы найдём кратчайший путь от узла 0 к узлу 1, потом к узлу 2, потом к узлу 3 и т. д. для каждого узла в графе.
Этот граф также можно представить в виде матрицы:
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 0 | 7 | 5 | ||
| 1 | 7 | 0 | 3 | 5 | |
| 2 | 5 | 3 | 0 | 4 | |
| 3 | 5 | 0 | 6 | ||
|
4 |
4 | 6 | 0 |
Таблица: слева "выходит из", сверху "куда направляется", и выставляем "вес" (пример: из "0" идёт в "1" с весом "7", из "0" идёт в "2" с весом "5", и больше из 0 не выходит ничего).
Если можно идти из одного узла в другой и обратно, это указывается в матрице (например: из 2 в 1 с весом 3 И из 1 в 2 с весом 3).
Пошаговый процесс нахождения минимального пути
Шаг 0. В этом примере исходным узлом будет узел 0 (т.к. расстояние от исходного узла до самого себя равно 0; но исходным узлом может быть любой узел, который вы выберете).
Шаг 1. Для первоначального представления расстояния от исходного узла до всех остальных узлов мы используем символ бесконечности, т.к. оно ещё не определено:
Делаем такой список узлов с расстояниями:
Расстояние:
0: 0
1: ∞
2: ∞
3: ∞
4: ∞
Мы начали с узла 0, значит, отмечаем этот узел как посещённый на диаграмме и вычёркиваем его из списка непосещённых узлов (дистанцию, которая равна нулю, уже обозначили).
Шаг 2. Теперь проверяем расстояние от узла 0 до соседних с ним узлов. Как это видно на картинке, это узлы 1 и 2 (см. красные линии), это наши возможные пути:
Путь 1 = 7, путь 2 = 5, т.к. путь 2 короче (дешевле), то выберем его.
Рассматриваем дальнейшие пути/узлы:
- путь от 2 до 1 равняется 3 (5 + 3 = 8, можно возле "1" поставить простым карандашом "8"),
- путь от 2 до 4 равняется 4 (5 + 4 = 9, можно возле "4" поставить простым карандашом "9").
Однако существует прямой путь из 0 в узел 1, который равняется 7, а 7 < 8, значит ставим 7 и выбираем этот путь.
Остались непосещёнными 3 и 4.
Непосещённый сосед 2 – это 4 (мы его ещё не посетили, мы только посчитали), в него можно попасть 5 + 4 = 9, ставим 9.
Непосещённый сосед 1 – это 3, в него можно попасть через:
- 0-1-3, это 7 + 5 = 12 (т.е. идём из 0 к 1 и потом к 3, и этот путь равен 12)
- 0-2-4-3 это 9 + 6 = 15 (идём из 0 к 2, потом к 4 и потом к 3, и этот путь равен 15)
- 0-2-1-3 это 5 + 3 + 5 = 13 (идём из 0 к 2, потом к 1 и потом к 3, и этот путь равен 13)
Естественно выбираем самый короткий путь (равный 12).
Путь 4 тоже оставляем тот, который был выбран, т.к. более короткого не видно (путь через 3 равен 12 + 6 = 18), ставим его посещённым.
Так как непосещённых узлов нет, всё готово!
Расстояние:
0: 0
1: 7
2: 5
3: 12
4: 9
Минимальное расстояние каждого узла, что мы нашли, представляет собой минимальное расстояние от этого узла до узла 0 (мы его выбрали в начале в качестве начального узла).
Минимальное остовное дерево
Ещё существует метод "Минимальное остовное дерево", и эти процессы часто путаются. Однако алгоритм Дейкстры отличается от метода Минимального остовного дерева тем, что кратчайшее расстояние между двумя вершинами может не включать все вершины графа; т.е. в алгоритме Дейкстры все вершины должны быть посещены.
Узнайте также про Квантовый компьютер и Криптовалюту.