Компьютерная математика: Часть 2. Теория графов. Волченская Т.В - 60 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

рассматриваемую вершину с постоянной пометкой возьмем вершину p, т.е.
положить
p = s.
Обновление пометок
ШАГ 2. Для вершин, входящих в прямое отображение вершины
р, т.е. для всех x
i
,
принадлежащих Г(
p), пометки которых временные, изменить пометки в
соответствии со следующим выражением:
L(x
i
) ← min [ L(x
i
), L(p)+c(p, x
i
) ].
Превращение пометки в постоянную
ШАГ 3. Среди всех вершин с временными пометками найти такую, для которой:
L(x
i
*
) = min [ L(x
i
) ].
ШАГ 4. Считать пометку вершины х
i
*
постоянной и положить р =
х
i
*
.
ШАГ 5(a). {
При нахождении пути от s к t}
• Если текущая вершина p является искомой, т.е. p = t, то L(p) является длиной
кратчайшего пути от
S к t. Останов.
• Если p ≠ t, перейти к шагу 2.
ШАГ 5(б) {
При нахождении путей от S ко всем вершинам }
• Если все вершины отмечены постоянными метками, то эти метки дают длины
кратчайших путей.
• Если некоторые метки являются временными, то следует перейти к шагу 2.
Как только длины кратчайших путей от вершины
s будут найдены, сами
пути можно получить при помощи рекурсивной процедуры (*). Так как вершина х
i
*
непосредственно предшествует вершине х
i
в кратчайшем пути от s к х
i
, то для
любой вершины х
i
соответствующую вершину х
i
*
можно найти как одну из
оставшихся вершин, для которой
L( x
i
*
) + c( x
i
*
, x
i
) = L( x
i
). (*)
Если кратчайший путь от
s до любой вершины х
i
является единственным, то
дуги (x
i
*
, x
i
) этого кратчайшего пути образуют ориентированное дерево с корнем
s. Если существует несколько кратчайших путей от s к какой-либо другой
вершине, то при некоторой фиксированной вершине х
i
*
соотношение (*) будет
выполняться для более чем одной вершины х
i
. В этом случае выбор может быть
либо произвольным (если нужен какой-то один кратчайший путь между
s и х
i
),
либо таким, что рассматриваются все дуги (х
i
*
, x
i
), входящие в какой-либо из
кратчайших путей, и при этом совокупность всех таких дуг образует не
ориентированное дерево, а общий граф, называемый
базой относительно s. 
рассматриваемую вершину с постоянной пометкой возьмем вершину p, т.е.
положить p = s.
Обновление пометок
ШАГ 2. Для вершин, входящих в прямое отображение вершины р, т.е. для всех xi,
принадлежащих             Г(p),   пометки      которых       временные,   изменить   пометки   в
соответствии со следующим выражением:
                                  L(xi) ← min [ L(xi), L(p)+c(p, xi) ].
Превращение пометки в постоянную
ШАГ 3. Среди всех вершин с временными пометками найти такую, для которой:
L(xi*) = min [ L(xi) ].
ШАГ 4. Считать пометку вершины хi* постоянной и положить р = хi* .
ШАГ 5(a). {При нахождении пути от s к t}
• Если текущая вершина p является искомой, т.е. p = t, то L(p) является длиной
   кратчайшего пути от S к t. Останов.
• Если p ≠ t, перейти к шагу 2.
ШАГ 5(б) { При нахождении путей от S ко всем вершинам }
• Если все вершины отмечены постоянными метками, то эти метки дают длины
   кратчайших путей.
• Если некоторые метки являются временными, то следует перейти к шагу 2.
       Как только длины кратчайших путей от вершины s будут найдены, сами
пути можно получить при помощи рекурсивной процедуры (*). Так как вершина хi*
непосредственно предшествует вершине хi в кратчайшем пути от s к хi, то для
любой вершины хi соответствующую вершину хi* можно найти как одну из
оставшихся вершин, для которой
                                    L( xi* ) + c( xi*, xi ) = L( xi ).    (*)
       Если кратчайший путь от s до любой вершины хi является единственным, то
дуги    (xi*, xi) этого кратчайшего пути образуют ориентированное дерево с корнем
s. Если существует несколько кратчайших путей от s к какой-либо другой
вершине, то при некоторой фиксированной вершине хi* соотношение (*) будет
выполняться для более чем одной вершины хi. В этом случае выбор может быть
либо произвольным (если нужен какой-то один кратчайший путь между s и хi),
либо таким, что рассматриваются все дуги (хi*, xi), входящие в какой-либо из
кратчайших путей, и при этом совокупность всех таких дуг образует не
ориентированное дерево, а общий граф, называемый базой относительно s.

Страницы