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

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

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

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

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

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

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

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

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

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

,

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

, откуда .

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

Дата добавления: 2014-01-03