A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
Cancel Create
brestprog / topics / dijkstra / dijkstra.md
- Go to file T
- Go to line L
- Copy path
- Copy permalink
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Cannot retrieve contributors at this time
222 lines (158 sloc) 9.21 KB
- Open with Desktop
- View raw
- Copy raw contents Copy raw contents Copy raw contents
Copy raw contents
Взвешенные графы. Алгоритм Дейкстры
topics/dijkstra/
В классических графах все рёбра считаются равноценными и длина пути соответствует количеству рёбер, которые он содержит. Однако часто в задаче каждому ребру соответствует некоторый параметр — длина ребра или стоимость прохождения по нему. В терминологии графов такой параметр называется весом ребра, а граф, содержащий взвешенные рёбра, взвешенным.
#3. Алгоритм Дейкстры (Dijkstra’s algorithm) | Алгоритмы на Python
Типичная задача для таких графов — поиск кратчайшего пути. Например, в этом графе кратчайший путь между вершинами $$1$$ и $$5$$ : $$1 — 4 — 3 — 5$$ , так как его вес равен $$30 + 20 + 10 = 60$$ , а вес ребра $$1 — 5$$ равен $$100$$ .
Классический алгоритм для поиска кратчайших путей во взвешенном графе — алгоритм Дейкстры (по имени автора Эдгара Дейкстры). Он позволяет найти кратчайший путь от одной вершины графа до всех остальных за $$O(M log N)$$ ( $$N, M$$ — количество вершин и рёбер соответственно).
Принцип работы алгоритма напоминает принцип работы BFS: на каждом шаге обрабатывается ближайшая ещё не обработанная вершина (расстояние до неё уже известно). При её обработке все ещё не посещённые соседи добавляются в очередь для посещения (расстояние до каждой из них рассчитывается как расстояние до текущей вершины + длина ребра). Главное отличие от BFS заключается в том, что вместо классической очереди используется очередь с приоритетом. Она позволяет нам выбирать ближайшую вершину за $$O(log N)$$ .
Анимация выполнения алгоритма Дейкстры для поиска кратчайшего пути из вершины $$a$$ в вершину $$b$$ :
С помощью псевдокода алгоритм Дейкстры описывается следующим образом:
ans = массив расстояний от начальной вершины до каждой. изначально заполнен бесконечностями (ещё не достигнута). ans[start] = 0 q = очередь с приоритетом, хранящая пары (v, dst), где dst — предполагаемое расстояние до v добавить (start, 0) в q пока q не пуста: (v, dst) = первая вершина в очереди (с минимальным расстоянием), и расстояние до неё извлечь (v, dst) из очереди если ans[v] < dst: //мы уже обработали эту вершину, используя другой путь перейти к следующей вершине для каждой v ->u: n_dst = dst + len(v -> u) //расстояние до u при прохождении через v если n_dst < ans[u]: //если мы можем улучшить ответ ans[u] = n_dst добавить (u, n_dst) в q
Как видите, в очереди с приоритетом хранится не только номер вершины, но и вычисленное расстояние до неё, по которому и ведётся сортировка. Также возможна ситуация, при которой одна и та же вершина будет помещена в очередь несколько раз с разным расстоянием (так как она достижима по нескольким рёбрам). В такой ситуации обрабатываем её только один раз (с минимальным возможным расстоянием).
Алгоритм Дейкстры
В нашей очереди с приоритетом должны храниться пары (вершина, расстояние до неё), причём отсортированы они должны быть по уменьшению расстояния. Для этого нужно использовать тип std::priority_queue, vector>, greater>> : первым элементом пары будет расстояние, а вторым — номер вершины.
Для хранения взвешенного графа в виде списка смежности для каждой вершины мы храним вектор пар (соседняя вершина, длина ребра до неё).
Реализация на C++:
using namespace std;
const int INF = 1e9 + 7;
vector> graph[100000]; int ans[100000];
for (int i = 0; i < n; i++) < ans[i] = INF; >ans[start] = 0; priority_queue, vector>, greater>> q; q.push(); while (!q.empty()) < pairc = q.top(); q.pop(); int dst = c.first, v = c.second; if (ans[v] < dst) < continue; >for (pair e: graph[v]) < int u = e.first, len_vu = e.second; int n_dst = dst + len_vu; if (n_dst < ans[u]) < ans[u] = n_dst; q.push(); > > > for (int i = 0; i
Реализация с восстановлением пути
Восстановление пути для алгоритма Дейкстры реализуется точно так же, как и для BFS: при успешном улучшении пути в вершину $$u$$ через вершину $$v$$ , мы запоминаем, что $$prev[v] = u$$ . После окончания работы алгоритма используем массив $$prev$$ для восстановления пути в обратном направлении.
Реализация на C++:
using namespace std;
const int INF = 1e9 + 7;
vector> graph[100000]; int ans[100000]; int pr[100000]; //prev
for (int i = 0; i < n; i++) < ans[i] = INF; pr[i] = -1; //Значение, обозначающее что из этой вершины возвращаться некуда >ans[start] = 0; priority_queue, vector>, greater>> q; q.push(); while (!q.empty()) < pairc = q.top(); q.pop(); int dst = c.first, v = c.second; if (ans[v] < dst) < continue; >for (pair e: graph[v]) < int u = e.first, len_vu = e.second; int n_dst = dst + len_vu; if (n_dst < ans[u]) < ans[u] = n_dst; pr[u] = v; q.push(); > > > vector path; int cur = end; path.push_back(cur); while (pr[cur] != -1) < cur = pr[cur]; path.push_back(cur); >reverse(path.begin(), path.end()); cout
Область применения алгоритма Дейкстры
Алгоритм Дейкстры является оптимальным для поиска пути практически в любых графах, но он имеет одно ограничение. Алгоритм Дейкстры неприменим для графов, содержащих рёбра с отрицательным весом. Для поиска кратчайшего пути в таких графах обычно используют алгоритм Форда-Беллмана.
Источник: github.com
Реализация алгоритма Дейкстры
Эта программа с исходником. Может помочь в решении задач. Использован алгоритм Дейкстры нахождения кратчайшего пути в графе.
Задача:
В ориентированной, неориентированной или смешанной (т. е. такой, где часть дорог имеет одностороннее движение) сети V найти кратчайший путь из заданной вершины i во все остальные вершины.
Алгоритм использует три массива из N (= числу вершин сети) чисел каждый. Первый массив A содержит метки с двумя значения: 0 (вершина еще не рассмотрена) и 1 (вершина уже рассмотрена); второй массив B содержит расстояния — текущие кратчайшие рас- стояния от до соответствующей вершины; третий массив с содержит номера вершин — k-й элемент С[k] есть номер предпоследней вершины на текущем кратчайшем пути из Vi в Vk. Матрица расстояний D[i,k] задает длины дуге D[i,k]; если такой дуги нет, то D[i,k] присваивается большое число Б, равное «машинной бесконечности».
Алгоритм Дейкстры
- (инициализация). В цикле от 1 до N заполнить нулями массив A; заполнить числом i массив C; перенести i-ю строку матрицы D в массив B,
A[i]:=1; C[i]:=0 (i — номер стартовой вершины) - (общий шаг). Hайти минимум среди неотмеченных (т. е. тех k, для которых A[k]=0); пусть минимум достигается на индексе j, т. е. B[j] Затем выполняются следующие операции:
A[j]:=1;
если B[k] > B[j] + D[j,k], то ( B[k] := B[j] + D[j,k]; C[k] := j )
(Условие означает, что путь Vi . Vk длиннее, чем путь Vi. Vj Vk).
(Если все A[k] отмечены, то длина пути от Vi до Vk равна B[k]. Теперь надо) перечислить вершины, входящие в кратчайший путь). - (выдача ответа). (Путь от Vi до Vk выдается в обратном порядке следующей процедурой:)
- 3.1. z:=C[k];
- 3.2. Выдать z;
- 3.3. z:=C[z]. Если z = О, то конец, иначе перейти к 3.2.
Для выполнения алгоритма нужно N раз просмотреть массив B из N элементов, т. е. алгоритм Дейкстры имеет квадратичную сложность: O(n2).
Более общий алгоpитм Флойда-Уоpшелла
находит кpатчайшие пути из всех во все:
for k:=1 to N do for i:=1 to N do for j:=1 to N do d[i,j]:=min(d[i,j], d[i,k]+d[k,j]);
Здесь d[i,j] — сначала длина дуги [i,j], а в конце — длина кpатчайшего пути.
Литература
В.М.Бондаpев, В.И.Рублинецкий, Е.Г.Качко. Основы пpогpаммиpования. Хаpьков/Ростов-на-Дону, 1997
Источник: www.zoonman.ru
Реализация алгоритма Дейкстры на C#
Всем привет, пишу данный топик как логическое продолжение данной статьи о максимальном потоке минимальной стоимости, в конце которой был затронут алгоритм Дейксты. Соглашусь с автором, что описание и различные реализации алгоритма можно найти без проблем, и «колесо» я не изобретаю, но тем не менее опишу здесь практическую реализацию на языке C#. Кстати отмечу, что использую LINQ, так что для работы необходим NET 3.5.
UPDНаконец-то подчистил код 🙂
Немного теории
Чтобы сразу не кидали камни в мой огород дам ссылку на очень хорошее описание алгоритма на таком незаметном ресурсе как Википедия :). Там вполне доступно описан алгоритм и особенно рекомендую посмотреть пример. Копировать оттуда материал считаю бессмысленно. Все, считаем что теорию изучили.