Теория игр и исследование операций. Модели, алгоритмы, сложность: Конспект лекций, страница 28

Получили ДКП.

Корректность алгоритма Дейкстры

D_k(i)  - текущее расстояние от i-й до 1-ой вершины, на k-ом шаге

O_k(i) – отец вершины i, на k-ом шаге

Свойства: (считаем, что вершины перенумеровав в порядке включения)

1.  D_k(i) не возрастает по k "i.

2.  D_k(k) не убывает по k при условии, что d_ij≥0.

3.  i → O(i) → O²(i) …→ 1 - текущий кратчайший путь из i в 1.

4.  D_k(i)= длина пути (из пункта 3) из i в 1.

5.  Для включенных вершин текущий путь по предкам является оптимальным.

6.  Если i₁ →i₂ →…→1 - это кратчайший путь из i₁ в 1, то D(i₁)=D(i₂)+

Справедливы утверждения:

1.  Задача нахождения всего ДКП имеет смысл в случае ориентированного ациклического графа или графа с циклами положительной длины. В неориентированном графе все ребра должны иметь неотрицательную длину.

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

№21. Алгоритм Флойда  (могут быть ребра отрицательной длины) :

D={d_ij≥0} – матрица расстояний, R={r_ij – кратчайшее расстояние между i и j}

Если на диагонали матрицы R на выходе алгоритма окажутся отрицательные элементы è есть цикл с отрицательной длиной, иначе циклов с отрицательной длиной нет и R_ij – кратчайшее расстояние между i и j.

“—“ аналог ∞.

                        Пример: Матрица расстояний:   На диагонали есть отрицательные

числа Þ $ цикл отрицательной длины Þ это не матрица кратчайших расстояний.

Поменяем порядок обхода: k=1, k=4, k=3, k=2