22.Нахождение кратчайшего пути между двумя вершинами в невзвешенном ориентированном графе. Волновой алгоритм.

Рассмотрим следующую задачу. В графе Г выделены две вершины: b (начальная) и e (конечная). Требуется найти все пути минимальной длины из b в e (если e достижима из b) либо установить недостижимость. Для решения этой задачи используется очень эффективный волновой алгоритм. Допустим, что по дугам графа может распространяться сигнал, причем по каждой дуге сигнал проходит за единицу времени. Выпустим в начальный 51 момент сигнал из вершины b, будем последовательно отмечать

вершины, до которых сигнал дойдет за 1,2,3,… единиц времени пока не будет отмечена вершина e. Остается отметить дуги, которые сигнал прошел по пути от b к e. При этом если в некоторый момент сигналу распространяться некуда, а вершина e не помечена, то она недостижима из b. С помощью этого подхода можно решить близкую задачу: найти длины кратчайших путей от вершины b до всех вершин графа. Волновой алгоритм тем самым состоит из двух этапов. Прямой ход позволяет найти длину кратчайшего пути (далее расстояние) от b до e (или до всех вершин графа), обратный ход позволяет восстановить пути. Прямой ход. На каждом шаге алгоритма вершины графа делятся на два подмножества – помеченных и не помеченных, причем на каждом шаге некоторые вершины переходят в класс помеченных. Пометками являются текущие состояния счетчика k. Также на каждом шаге формируется множество вершин – фронт волны (ФВ).

Шаг 0. k:=0, ФВ:={b}.

Шаг 1. Вершины из множества ФВ пометить числом k.

Шаг 2. Если {eÎФВ или ФВ=Æ} то прямой ход завершен

иначе шаг 3.

Шаг 3. ФВ:={uÎV: u не помечена, $vÎФВ: (v,u)ÎE}, k:= k+1.

Переход к шагу 1.

Если вершина e имеет пометку (ke), то реализуем обратный

ход. На каждом шаге строится множество вершин «Возврат» (В) и

отмечается некоторое семейство дуг.

Шаг 4. k:=k e, В:={e}.

Шаг 5. k:=k –1; отметить дуги, ведущие из вершин с пометкой

k, в вершины, принадлежащие множеству В; В:={множество

начальных вершин отмеченных дуг}.

Шаг 6. Если k=0 то конец иначе переход к шагу 5.

По окончании работы алгоритма подграф, образованный

отмеченными дугами и соответствующими вершинами, содержит

все нужные кратчайшие пути.

23.Взвешенный граф. Нахождение кратчайшего пути между двумя заданными вершинами во взвешенном ориентированном графе. Алгоритм Дейкстры.

Взвешенный (другое название: размеченный) граф (или орграф) - это граф (орграф), некоторым элементам которого (вершинам, ребрам или дугам) сопоставлены числа. Наиболее часто встречаются графы с помеченными ребрами. Числа-пометки носят различные названия: вес, длина,стоимость.

Замечание: Обычный (не взвешенный) граф можно интерпретировать как взвешенный, все ребра которого имеют одинаковый вес 1.

Длина пути во взвешенном (связном) графе - это сумма длин (весов) тех ребер, из которых состоит путь. Расстояние между вершинами - это, как и прежде, длина кратчайшего пути. Например, расстояние от вершины a до вершины d во взвешенном графе.

Путем в орграфе называется последовательность вершин v1,v2,...,vn, для которой

существуют дуги (v1,v2)(v2,v3)... (vn-1,vn). Длина пути - количество дуг,

составляющих путь. Если граф является взвешенным, то длина пути определяется

как сумма весов дуг.

Алгоритм Дейкстры решает задачу о кратчайших путях из одной вершины для взвешенного ориентированного графа G = (V, E) с исходной вершиной s, в котором веса

всех рёбер неотрицательны ( (u, v) ≥ 0 для всех (u, v) E).

Формальное объяснение В процессе работы алгоритма Дейкстры поддерживается множество S V, состоящее из вершин v, для которых δ(s, v) уже найдено. Алгоритм выбирает вершину u V\S с наименьшим d[u], добавляет u к множеству S и производит релаксацию всех рёбер, выходящих из u, после чего цикл повторяется. Вершины, не лежащие в S , хранятся в очереди Q с приоритетами, определяемыми значениями функции d. Предполагается, что граф задан с помощью списков смежных вершин.

Не формальное объяснение

Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещенные.

Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае из еще не посещенных вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, соединенные с вершиной u ребрами, назовем соседями этой вершины. Для каждого соседа рассмотрим новую длину пути, равную сумме текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученная длина меньше метки соседа, заменим метку этой длиной. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг.