Поделиться Поделиться

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

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

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

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

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

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

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

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

Матричный

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

Метод Форда-Беллмана решения задачи о кратчайшем пути в графе - Инвестирование - 5 n-число вершин, m – число дуг или ребер

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

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

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

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

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

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

Неорграф:

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

Орграф:

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

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

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

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

Неорграф:

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

Орграф:

Путем в графе называется упорядоченная последовательность дуг μ = (U1, …, Un), в которой конец предыдущей дуги совпадает с началом последующей. Путь у которого начальные и конечные вершины совпадают – контур . Длина цепи – число ребер в цепи. Граф называется связным , если любая пара его вершин соединены цепью. Минимальная длина цепи, соединяющая вершины xi и xj называется расстоянием.Метод Форда-Беллмана решения задачи о кратчайшем пути в графе - Инвестирование - 12 Максимальное расстояние между вершинами графа называется диаметром графа.Метод Форда-Беллмана решения задачи о кратчайшем пути в графе - Инвестирование - 13 . Цепь (неорграф) называют составной , если в ней повторяется хотя бы одно ребро; сложной , если повторяется хотя бы одна вершина. Простой цикл называется гамильтоновым , если он проходит через каждую вершину графа ровно 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, то данное соотношение будет выполняться для нескольких вершин. В этом случае выбор пути может быть произвольным.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

← Предыдущая страница | Следующая страница →