avangard-pressa.ru

Метод Форда-Беллмана решения задачи о кратчайшем пути в графе - Логика

Способы задания графов

Геометрический (графический)

Вершины изображают точками на плоскости, а ребра – линиями, соединяющими соответствующие точки. Для изображения дуги используется линия со стрелкой, указывающей направление от начала к концу дуги.

Теоретико-множественный


Матричный

А) Матрица инцидентности

n-число вершин, m – число дуг или ребер

Для неорграфа:

Б) Матрица смежности

Неорграф:

Орграф:

Маршруты, цепи, циклы

Маршрутом в графе называется {x1,r1,x2,r2,…xn}

чередующиеся последовательность вершин и ребер/дуг.

Неорграф:

Цепьюρ=(r1, … rn) называется упорядоченная последовательность ребер в которой у каждого ребра ri одна из граничных вершин является граничной вершиной ri-1, а другие ri+1. Если вершины и ребра в цепи различны, то маршрут называют простой цепью. Замкнутая цепь называется циклом, а замкнутая простая цепь называется простым циклом.

Орграф:

Путем в графе называется упорядоченная последовательность дуг μ = (U1, …, Un), в которой конец предыдущей дуги совпадает с началом последующей. Путь у которого начальные и конечные вершины совпадают – контур. Длина цепи– число ребер в цепи. Граф называется связным, если любая пара его вершин соединены цепью. Минимальная длина цепи, соединяющая вершины xi и xj называется расстоянием. Максимальное расстояние между вершинами графа называется диаметром графа. . Цепь (неорграф) называют составной, если в ней повторяется хотя бы одно ребро; сложной, если повторяется хотя бы одна вершина. Простой цикл называется гамильтоновым, если он проходит через каждую вершину графа ровно 1 раз. В орграфе путь, проходящий через все вершины ровно 1 раз, называется гамильтоновым, если у него начальная и конечная вершина совпадают, то гамильтонов контур.

Алгоритм Дейкстры.

Пусть l(xi) – пометка вершины xi.

Шаг 1. Присвоение начальных значений. Положить l*(s)=0 и считать эту пометку постоянной. Положить l(xi)=∞ (бесконечность) для всех xi¹s и считать эти пометки временными. Положить р=s.

Шаг 2. Обновление пометок. Для всех вершин xiÎГ(р), имеющих временные пометки, изменить пометки в соответствии с выражением:

l(xi) = min{l(xi), l(p) + c(p, xi)}. (2.3)

Шаг 3. Превращение пометки в постоянную. Среди всех вершин с временными пометками найти такую, для которой l*(xi) = min{l(xi)}.

Шаг 4. Считать пометку вершины xi* постоянной и положить p = xi*.

Шаг 5. Если р=t, то l*(р) является длиной кратчайшего пути. Конец.
Если р¹t, перейти к шагу 2.

Как только длина кратчайшего пути от s до t будет найдена [она будет постоянной пометкой вершины l*(t)], сами пути можно получить с помощью рекурсивной процедуры. Так, для вершины xk, непосредственно предшествующей вершине t в кратчайшем пути от s к t, будет соблюдаться отношение: l*(xk) + c(xk, t) = l*(t).

Таким образом, для любой вершины xi можно найти предшествующую вершину xk, принадлежащую пути m(s, t), для которой справедливо:

l*(xk) + c(xk, xi) = l*(xi). (2.4)

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

Метод Форда-Беллмана решения задачи о кратчайшем пути в графе.

Алгоритм Ф.Б. позволяет находить кратчайшие пути от источника S до любой вершины, при этом веса дуг могут быть как “+”, так и “-“.

Исходные данные: граф C помечен дугами, а результат помечен вершинами.

1) Присвоение начального значения меток

Установить номер итерации k=0, присвоить начальное значение меток следующим образом:

2) Обновление пометки вершин

Для каждой вершины Xj =Г(S) установить пометку следующим образом:

Где Tj = Г-1 множество вершины, которые входят в Xj и связан с вершиной X

3) Проверка условий окончания

Если k <= n-1 и Пк+1 (Xj) != Пк (Xj) хотя бы для 1 вершины, то переход к шагу 4 если

Пк+1 (Xj) = Пк (Xj), то конец алгоритма.

4) Подготовка к следующей итерации

Определить множество S, как множество таких X, что

Пометки П (Xi) у всех вершин графа характеризуют расстояние от источника Х1 до данной вершины.