|
Задача нахождения кратчайшего пути. Алгоритм Дейкстры
Пусть есть ориентированный граф, у которого все дуги имеют неотрицательные метки (стоимости дуг), а одна вершина определена как источник. Задача состоит в нахождении стоимости кратчайших путей от источника ко всем другим вершинам графа G (здесь длина пути определяется как сумма стоимостей дуг, составляющих путь). Эта задача часто называется задачей нахождения кратчайшего пути с одним источником.
Пример. Рассмотрим работу алгоритма Дейкстры на примере графа, показанного на рисунке. Пусть требуется найти расстояния от 1-й вершины до всех остальных. Кружками обозначены вершины, линиями — пути между ними (ребра графа).
В кружках обозначены номера вершин, над ребрами обозначена их «цена» — длина пути. Рядом с каждой вершиной красным обозначена метка — длина кратчайшего пути в эту вершину из вершины 1
| Первый шаг. Минимальную метку имеет вершина 1. Ее соседями являются вершины 2, 3 и 6.
| Первый по очереди сосед вершины 1 — вершина 2, потому что длина пути до нее минимальна. Длина пути в нее через вершину 1 равна кратчайшему расстоянию до вершины 1 + длина ребра, идущего из 1 в 2, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, поэтому новая метка 2-й вершины равна 7.
| Аналогичную операцию проделываем с двумя другими соседями 1-й вершины — 3-й и 6-й.
|
| Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит (то, что это действительно так, впервые доказал Дейкстра). Вычеркнем её из графа, чтобы отметить, что эта вершина посещена.
| Второй шаг. Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.
| Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю. Соседями вершины 2 являются 1, 3, 4.
Первый (по порядку) сосед вершины 2 — вершина 1. Но она уже посещена, поэтому с 1-й вершиной ничего не делаем.
| Следующий сосед вершины 2 — вершины 4 и 3. Если идти в неё через 2-ю, то длина такого пути будет = кратчайшее расстояние до 2 + расстояние между вершинами 2 и 4 = 7 + 15 = 22. Поскольку 22<∞, устанавливаем метку вершины 4 равной 22.
| Ещё один сосед вершины 2 — вершина 3. Если идти в неё через 2, то длина такого пути будет = 7 + 10 = 17. Но текущая метка третьей вершины равна 9<17, поэтому метка не меняется.
| Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и помечаем её как посещенную.
| Третий шаг. Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим такие результаты:
| Повторяем шаг алгоритма для оставшихся вершин (Это будут по порядку 6, 4 и 5).
|
|
|
| | Завершение выполнения алгоритма. Алгоритм заканчивает работу, когда вычеркнуты все вершины. Результат его работы: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й — 9, до 4-й — 20, до 5-й — 20, до 6-й — 11.
Поскольку алгоритм Дейкстры всякий раз выбирает для обработки вершины с наименьшей оценкой кратчайшего пути, можно сказать, что он относится к «жадным» алгоритмам.
Дан орграф G с множеством вершин V(G). Массив w — это двумерный массив стоимостей, где элемент w[i, j] равен стоимости дуги i ® j. Если дуги i ® j не существует, тоw[i, j] ложится равным ¥, т.е. большим любой фактической стоимости дуг. В графе выделены две вершины, s и f, начало и конец пути.
В общем случае может существовать несколько различных путей из s в f. С каждой вершиной v графа связана переменная l[v], называемая меткой. На каждом шаге l[v] содержит длину текущего кратчайшего особого пути к вершинеv.В процессе работы метка изменяется (временная метка). Метка становится постоянной, когда найден самый короткий путь от вершины s к вершине v. Алгоритм заканчивает работу, когда постоянной становится метка от s до f.
Переменная p принимает в качестве своих значений вершины графа. Н – множество вершин, имеющих временные метки.
Алгоритм Дейкстры
procedure Short(s, f);
...
Begin
for v Î V(G) do l[v]:= ¥ ; { инициализация l }
l[s]:=0;
p:=s; // рабочая переменная
H:=V(G)-s; // множество вершин, имеющих временные метки
While p <> f do begin
for v Î Out(p) Ç H do l[v]:= (min[l[v],l[p]+w[p,v]);
m:=f; // m – минимальная метка
for v Î H do if l[m]>l[v] then m:=v;
H:=H-m; p:=m;
end;
end;
Задание. Для ориентированного графа нарисовать матрицу смежности. Используя алгоритм Дейкстры, найти минимальные путь между вершиной №1 и всеми остальными. Выполнение алгоритма описать пошагово. В результате должен быть представлен сам путь (пути), а не только минимальные значения.
|
|
|
|
|
| В начале l
(метки вершин):
Н={2, 3, 4, 5}
|
p=1
|
¥
|
¥
|
¥
|
¥
| Шаг 1
l (метки вершин):
Н={3, 4, 5}
|
|
{1, 2}
p=2
| ¥
|
{1, 4}
|
{1, 5}
| Шаг 2
l (метки вершин):
Н={ 3, 5}
|
|
|
{1, 2, 3}
|
{1, 4}
p=4
|
{1, 5}
| Шаг 3
l (метки вершин):
Н={5}
|
|
|
{1, 4, 3}
p=3
|
|
{1, 4, 5}
| Шаг 4
l (метки вершин):
Н={ }
|
|
|
|
|
{1, 4, 3, 5} p=5
|
Несложно внести изменения в алгоритм так, чтобы можно было определить сам кратчайший путь (т.е. последовательность вершин) для любой вершины. Для этого надо ввести еще один массив Р1 вершин, где P1[v] содержит вершину, непосредственно предшествующую вершине v в кратчайшем пути. В программе надо записать условный оператор с условием l[p]+w[p,v]<l[v], при выполнении которого элементу P1[v] присваивается значение p. После выполнения алгоритма кратчайший путь к каждой вершине можно найти с помощью обратного прохождения по предшествующим вершинам массива Р1.
Type graph=array [1..nn,1..nn] of integer;
Не нашли, что искали? Воспользуйтесь поиском по сайту:
©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|