quot; vÎV Þ d[v] = dmin(s,v)

↑

▷ Содержание

⇐ ПредыдущаяСтр 2 из 2

" vÎV Þ d[v] = dmin(s,v)

Доказательство,

Покажем, что на любой итерации цикла

1) Для вершин vÎS (S – множество уже обработанных вершин) уже выполняется утверждение теоремы, т.е. d[v] = d_min(s,v), и, кроме того, к этим вершинам существуют кратчайшие пути только из вершин S.

2) Для вершин vÎ Q=V\S значение d[v] равно наименьшему весу пути из s в v, если учитывать только те особые пути, в которых все вершины (кроме последней) лежат в S(если таких путей нет, то d[v] = ¥)

Для начальной итерации, когда в S только одна вершина s, свойства 1 и 2 справедливы. Покажем выполнимость этих утверждений для любой итерации. Пусть u есть вершина из Q=V\S с минимальным значением d[u]. Покажем, что особый путь из sв uвеса d[u]является кратчайшим для u.  Пусть существует другой путь из sв u. Рассмотрим первую вершину yÏS. По свойству 1 и предположения индукции вес пути из sв yне меньше d[y] и, кроме того, d[y]³d[u](условие выбора u). Это означает, что вершину u можно добавить в S и свойство 1 не нарушится.

Расширение множества S'=SÈ{u} сопровождается уточнением расстояний до вершин множества Q

"vÎQ Þ d'[v] = min(d[v],d[u]+w(u,v))

Оба значения, из которых определяется величина d'[v], есть веса особых путей из sв v. Покажем, что вес любого особого пути из sв uне меньше d'[v]. На самом деле, пусть xÎS' есть вершина, предшествующая v. Тогда либо xÎSи тогда вес пути не меньше d'[v]по свойству 1, либо x=uи необходимое условие следует из правила вычисления d'[v].

Итак, условия 1 и 2 выполняются на всех итерациях цикла, в том числе, и по завершении работы алгоритма Дейкстры.

Количество операций пересчета весов путей до вершин графа пропорционально числу вершин N

Количество итераций алгоритма также совпадает с N

Ä  T_max = O(N²)

Если для представления вектора весов d использовать приоритетную очередь на основе двоичной кучи, то можно получить оценку

Ä  T_max = O(M log N),

где M есть общее количество вершин в графе.

Познавательные статьи:



Техника нижней прямой подачи мяча

Комплекс физических упражнений для развития мышц плечевого пояса

Стандарт Порядок надевания противочумного костюма

Общеразвивающие упражнения без предметов