Лекция 7. Задача о кратчайшем пути в ориентированном графе. Алгоритм Форда-Беллмана. Алгоритм Дейкстры (1162203)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Методы дискретной оптимизацииЗадача о кратчайшем пути вориентированном графе. АлгоритмФорда-Беллмана. Алгоритм Дейкстры.1 / 12Основные понятия. Постановка задачиОпределение.Взвешенный орграф Ḡ = (V, E, c) называется сетью. Ориентированныймаршрут называется путем.Определение.Пусть P – некоторый (v, w)-путь:v = v0 → v1 → . . .

→ vk = wТогда l(P ) = c(e1 ) + c(e2 ) + · · · + c(ek ) называется длиной пути P , где ei –ребро перехода от вершины vi−1 к вершине vi .(u, w)-путь с наименьшей длиной называется кратчайшим.Задача о кратчайшем пути (ЗКП)Задача о кратчайшем пути между фиксированными вершинами: взаданной сети Ḡ с двумя выделенными вершинами s и t найтикратчайший (s, t)-путь.2 / 12Общий случай. Алгоритм Форда-БеллманаОбщие замечания: Будем предполагать, что если вершины v и w неявляются смежными в Ḡ, то c(v, w) = ∞. Также будем считать, чторассматриваемая сеть не содержит контуров отрицательной длины.Схема вычисления:1.

Размечаются все вершины сети и вычисляются длины кратчайшихпутей от s до всех вершин.2. Используя специальные метки, обратным ходом строится кратчайшийпуть.Замечание. Для вычисления длины кратчайшего пути от s до tнеобходимо вычислить длины кратчайших путей от s до всех вершин.3 / 12Алгоритм Форда-БеллманаЛестер Форд (1956), Ричард Беллман (1958).Основная идея: поэтапное вычисление кратчайших расстояний.Обозначим через dk (v) длину кратчайшего среди всех (s, v)-путей,содержащих не более k ребер. Тогдаd1 (v) ≥ d2 (v) ≥ · · · ≥ dn−1 (v).В графе нет контуров отрицательной длины, следовательно, кратчайший(s, v)-путь не может содержать более n − 1 ребра и dn−1 (v) – длинакратчайшего пути из s в v.Для вычисления dn−1 (v) достаточно последовательно вычислять dk (v) длявсех k = 1, ..., n − 1:d1 (v) = c(s, v), ∀v ∈ Vdk+1 (v) = min{dk (v), dk (w) + c(w, v)|w ∈ V }4 / 12Алгоритм Форда-БеллманаОписанные вычисления возможно организовать с помощью одномерногомассива D длины n.

Положив D[v] = c(s, v), ∀v ∈ V , получимD[v] = d1 (v).Просматривая далее все вершины v, пересчитаем значения D[v]следующим образом:D[v] = min{D[v], D[w] + c(w, v)|w ∈ V }.После первого пересчета значений D[v] для всех v, получим, чтоD[v] ≤ d2 (v). Повторив n − 2 раза пересчет D[v], будем иметь равенстваD[v] = dn−1 (v), ∀v ∈ VПостроение кратчайших путей будем вести с помощью одномерногомассива P revious длины n, где P revious[v] дает имя вершины,предпоследней в кратчайшем (s, v)-пути.5 / 12Алгоритм Форда-БеллманаФормальное описание алгоритмаВХОД: Ḡ = (V, E, c) – сеть, A – матрица весов порядка n, вершины s и t.ВЫХОД: D[v] – кратчайшие расстояния от s до всех v ∈ V , S –кратчайший (s, t)-путь или сообщение, что искомого пути не существует.1.

procedure Distance2. begin3. D[s] = 0; P revious[s] := 0;4. for v ∈ V \{s} do5.begin D[v] := A[s, v]; P revious[v] := s end6. for k := 1 to n − 2 do7.for v ∈ V \{s} do8.for w ∈ V do9.if D[w] + A[w, v] < D[v] then10.begin11.D[v] := D[w] + A[w, v];12.P revious[v] := w13.end14. end6 / 12Алгоритм Форда-Беллмана15. begin16.Distance17.if D[t] < ∞ then18.begin19.S := nil; S ⇐ t; v := t;20.while P revious[v] 6= 0 dobegin v := P revious[v]; S ⇐ v end21.22.23.endelse writeln("Not exists");24.

endСложность алгоритма Форда-Беллмана: O(n3 ) = O((n − 2) · (n − 1) · n).7 / 12Пример8 / 12Алгоритм ДейкстрыЭдсгер Дейкстра (1959)Алгоритм Дейкстры позволяет вычислять в сети с неотрицательнымивесами кратчайшие расстояния от фиксированной вершины s до всехостальных вершин и находить кратчайшие пути более эффективно, чемалгоритм Форда-Беллмана. В основе алгоритма Дейкстры лежит принцип«жадности», заключающийся в последовательном вычислениикратчайших расстояний сначала до ближайшей к s вершине, затем доследующей ближайшей и т.

д.Обозначим через d(v) расстояние от s до v, т. е. длину кратчайшего(s, v)-пути в сети Ḡ.Первая ближайшая к вершине s вершина v это сама вершина s и d(s) = 0.Пусть ближайшие k вершин к вершине s определены и для всех нихвычислены кратчайшие расстояния d(v), т.е. определено множествоS = {v1 = s, v2 , ..., vk }, причем выполняются неравенства:1)0 = d(v1 ) ≤ d(v2 ) ≤ ...

≤ d(vk )2)d(vk ) ≤ d(v), ∀v ∈ V \S9 / 12Алгоритм ДейкстрыНайдем следующую ближайшую к s вершину сети Ḡ. Для каждогоw ∈ V \S положимD(w) = min{d(v) + c(v, w)|v ∈ S}D(w) определяет длину минимального (s, w)-пути среди всех (s, w)-путей,все вершины в котором, кроме w, принадлежатS.Выберем такую вершину w∗ ∈ V \S что выполнено условие:D(w∗ ) = min{D(w)|w ∈ V \S}.Вершина w∗ является самой близкой к s среди всех вершин, не входящихв S (она является следующей (k + 1)-й ближайшей к s вершиной), икратчайшее расстояние от вершины s до вершины w∗ в точности равноD(w∗ ) т.е. d(w∗ ) = D(w∗ ).Таким образом, выбирая вершину w ∈ V \S с минимальным значениемD[v] и добавляя к S, мы расширяем множество вершин, до которыхвычислено расстояние, на один элемент.

Повторяя процесс расширенияn − 1 раз, мы вычислим расстояние до всех вершин Ḡ10 / 12Алгоритм ДейкстрыФормальное описание алгоритмаВХОД: Ḡ = (V, E, c) – сеть, A – матрица весов порядка n, вершина s.ВЫХОД: D[v] – кратчайшие расстояния от s до всех v ∈ V , P revious[v] –предпоследняя вершина в кратчайшем (s, v)-пути.1.

begin2. D[s] = 0; P revious[s] := 0; F := V \{s}3. for v ∈ F do4.begin D[v] := A[s, v]; P revious[v] := s end5. for k := 1 to n − 1 do6.begin7.w := M in(F ); F := F \{w} // M in(F ) = Arg minw∈F D(w)8.for v ∈ F do9.if D[w] + A[w, v] < D[v] then10.begin11.D[v] := D[w] + A[w, v];12.P revious[v] := w13.end14.end15. end11 / 12Алгоритм Дейкстры. ПримерСложность алгоритма Дейкстры:O(n + (n − 1) + ... + 1) = O(n(n − 1)/2) = O(n2 ).Пример12 / 12.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций