Элементы теории графов и их технические приложения - 47 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

47
определяемой соотношением
=
)(rl
∑
=
K
i
i
el
1
)(. Требуется для произвольных вершин a
и b графа G найти путь
ab
r , причем такой, чтобы его полная длина была
наименьшей.
Общее правило нахождения кратчайшего пути в графе состоит в том, чтобы
каждой вершине
i
x
приписать индекс
i
λ
, равный длине кратчайшего пути из
данной вершины в конечную. Сложность этой процедуры заключается в том , что
путь, проходящий через наименьшее число вершин, часто имеет большую длину,
чем некоторые обходные пути. Например, в графе рис. 60, изображающем карту
дорог, прямой путь, из вершины помеченный звездочкой в конечную вершину,
имеет длину
=l 12, в тоже время обходной путь через вершину, отмеченную
треугольником имеет длину
=l 10.
Рис. 60. Карта дорог. Цифры у ребер указывают время проезда не каждой из
дорог.
Приписывание индексов вершинам производится в следующем порядке:
1) конечной вершине
0
xb = приписывается индекс 0
0
=
λ
, остальные вершины
i
x
помечаются индексами
i
λ , которым полагаем
∞
=
i
λ
)0(
≠
i ;
2) ищем такую дугу ),(
ji
xx , для которой ),(
jiij
xxl>
−
λ
λ
и заменяем индекс
j
λ
индексом
jjiij
xxl λλλ <+=
′
),(. Продолжаем этот процесс замены индексов до тех
пор, пока остается хоть одна дуга, для которой можно уменьшить
j
λ .
Приписанные вершинам индексы обладают двумя свойствами:
1. Для произвольного ребра ),(
SK
xx обязательно выполняется условие
),(
SKKS
xxl≤− λλ
.
2. Для произвольной вершины
p
x с индексом
p
λ
найдется вершина
q
x , соединенная
ребром с
p
x , такая, что ),(
pqqp
xxl=− λλ .

Страницы