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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

48
Рис. 61.
На основе указанных свойств можно сформулировать правило нахождения
кратчайшего пути.
Пусть
ax
n
= - начальная вершина с индексом
n
λ
ищем вершину
1
p
x , такую,
что ),(
11
nppn
xxl=− λλ . Далее ищем вершину
2
p
x такую, что ),(
1221
pppp
xxl=− λλ и
т.д. до тех пор, пока не дойдем до конечной вершины
bx
=
0
.
Путь ),,...,,,(
00
21
xxxxxr
K
pppn
= длина которого
n
λ
является кратчайшим
(последовательность индексов должна уменьшаться).
Рассмотрим указанную процедуру на графе рис. 60, результат которой приведен
на рис. 61.
Конечной вершине
0
xb = приписываем индекс 0)(
0
=x
λ
. Вершине
1
x ,
непосредственно примыкающей к
0
x приписываем индекс 2)(
1
=
xλ , т.к.
кратчайший путь 2),(
01
=xxl . Вершине
2
x приписываем индекс 7)(
2
=
xλ , т.к.
кратчайший путь 7),(
02
=xxl . Вершине
3
x приписываем индекс 10)(
3
=
xλ , т.к.
кратчайший путь
=
+
+
= ),(),(),(),(
01155303
xxlxxlxxlxxl
.1+7+2=10 Вершине
4
x приписываем индекс 10)(
4
=
x
λ
, т.к. кратчайший путь
1073),(),(),(
033404
=
+=+= xxlxxlxxl . Вершине
5
x приписываем индекс 9)(
5
=
x
λ
,
т.к. кратчайший путь 927),(),(),(
011505
=
+
=
+
= xxlxxlxxl . Для вершины
6
x
17278),(),(),(),(
01155606
=
+
+
=
++= xxlxxlxxlxxl , поэтому 17)(
6
=xλ . Для
вершины
7
x имеем 725),(),(),(
011707
=
+
=
+
= xxlxxlxxl , т.е. 7)(
7
=xλ . Поскольку
20173)(),()()(),(
6696909
=
+
=
+
=
−= xxxlxxxxl
λ
λλ , то 20)(
9
=xλ . Далее
24204),()()(
9898
=+
=
+= xxlxx λλ
;
2010352)(),(),(),()(
33121211111010
=
+
+
+
=
+
++= xxxlxxlxxlx
λ
λ ;
181035)(),(),()(
3312121111
=
+
+
=
++= xxxlxxlx λλ
;
13103)(),()(
331212
=+=+= xxxlx λλ ;

Страницы