Рассмотрим следующую задачу. В графе Г выделены две вершины: b (начальная) и e (конечная). Требуется найти все пути минимальной длины из b в e (если e достижима из b) либо установить недостижимость.
Для решения этой задачи используется очень эффективный волновой алгоритм. Идея его простая. Допустим, что по дугам графа может распространяться сигнал, причем по каждой дуге сигнал проходит за единицу времени. Выпустим в начальный момент сигнал из вершины 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.
По окончании работы алгоритма подграф, образованный отмеченными дугами и соответствующими вершинами, содержит все нужные кратчайшие пути.
Введенное понятие графа целесообразно обобщить. Например, если граф описывает какие-либо населенные пункты и соединяющие их дороги, то информации о наличии или отсутствии дорог явно недостаточно для принятия решения о том, как ехать: как минимум, надо знать длину дороги. Поэтому целесообразно ввести следующее понятие.
ОПРЕДЕЛЕНИЕ 24. Взвешенным графомназывается граф, каждой дуге которого сопоставлено неотрицательное число – вес дуги. Если дуги (a,b) в графе нет, то мы будем считать, что вес дуги бесконечный. «Обычный» граф это частный случай взвешенного графа, веса дуг в котором равны 1.
Взвешенный граф можно задать аналогом матрицы смежности (название сохраняется), в которой соответствующие элементы равны весам дуг.
Для практики важную роль играет следующая задача. Найти путь, соединяющий вершину b с e, для которого минимальна сумма весов дуг (вес пути). Для решения этой задачи в середине 20 века было разработано множество эффективных алгоритмов. Опишем один из них (алгоритм Дейкстры). Существенное отличие от волнового алгоритма состоит в том, что в стандартной форме алгоритм Дейкстры строит один путь минимального веса даже в том случае, если их несколько.
Идея алгоритма Дейкстры заключается в следующем. На каждой итерации вершины также делятся на два семейства: с постоянной и временной пометкой, причем одна из вершин приобретает постоянную пометку. Временные пометки могут обновляться (они не возрастают для каждой вершины). Постоянная пометка это минимальный вес пути из вершины b до данной, если в качестве промежуточных используются только вершины, имеющие постоянную пометку.
Опишем алгоритм Дейкстры более формально.
Пометку вершины с номером i будем обозначать через q(i), на каждой итерации определена вершина с номером p* (базовая вершина) - это та из вершин, которая на данной итерации приобрела постоянную пометку. Будем использовать обозначение Г(i) – это множество вершин графа, до которых можно дойти по одной дуге из вершины с номером i.
Шаг 0. Полагаем q(b)=0, пометка вершины b постоянная, p*:= b, у остальных вершин пометки временные, равные ¥.
Шаг 1 (обновление пометок). Для всех вершин из множества Г(p*) с временными пометками q(i):=min{q(i), q(p*)+c(p*,i)} (c(p*,i) – вес дуги).
Шаг 2. p*:=вершина с минимальной временной пометкой, пометка вершины p* становится постоянной.
Шаг 3. Если {p*=e или процесс невозможно продолжить} то конец иначе переход к шагу 1.
Проще всего реализовать этот алгоритм в виде таблицы.
Пометка вершины e – это минимальный из весов путей, соединяющих b с e. Если эта пометка конечная, то для восстановления соответствующего пути необходимо обратным ходом определить, на какой итерации последний раз обновлялась пометка вершины e и какая вершина была на этой итерации базовой, затем то же самое проделать для этой вершины и т.д. Если пометка бесконечная, то e недостижима из b. Этот алгоритм, естественно, можно использовать и для нахождения минимальных весов путей из данной вершины во все остальные.