double arrow

Обоснование алгоритма

Докажем, что после конечного числа применений правила для каждой дуги графа станет справедливым неравенство .

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

Предположим, что после того, как применено правило раз , станет справедливым утверждение, что для . На шаге какая-то вершина получит новую метку . Но в силу предположения индукции , кроме того, ; поэтому .

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

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

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

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

Докажем, что путь — кратчайший. Для этого рассмотрим произвольный путь: , соединяющий решину с . Имеем неравенства:

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

,

так как . В то же время, по построению пути имеем:

, откуда .

Пример. В графе (рис. 9) легко установить, что кратчайший путь, соединяющий вершины и , имеет длину .


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: