Решение задачи

33. Построение графа

Построим граф (рис. 1), соответствующий матрице смежности (табл. 2).

Рис. 1

34. Определение кратчайших расстояний от вершины jcj до всех остальных

Результаты вычислений будем представлять в таблице (табл. 3), в которой имена столбцов соответствуют номерам шагов алгоритма.

					"абл. 3
	0	1	2	3		4
Xj	0*
х2	00
*3	00
Х4	00
л:5	оо

Предварительно всем вершинам графа, кроме вершины х_ь присвоим вре­менные метки, равные бесконечности: L(x₂) = Цх₃) = Цх₄) = Цх₅) = оо, а вершине Х\ присвоим постоянную метку L*(x\) = 0. Занесем метки в нулевой столбец табл. 3.

Выполним последовательность следующих шагов:

Шаг 1

а) Определим множество вершин графа, смежных с вершиной xi (рис. 1, табл. 2):

S(a;i)= {х₂,х₄,х₅}.

в) Для каждой вершины, принадлежащей множеству S(x\), вычислим новые вре­менные метки L(xj), равные min{ L^CT(xj), L*(X]) + R]j}, где L^CT(xj) - старая вре­менная метка вершины Xj, L*(x\) = 0 - постоянная метка вершины Х\, Ry- вес ребра (xj, х,). Вычисления выполним в табл. 3-а.

L *(x_t) = 0 Табл. 3-а

V\Xj)	L*(xi)+Ru		min{LCT(jC/), ( L*(x0 +
L(x 2) = 00	L*(x 1) + R\2 —	0 + 4 = 4	min{oo, 4} = 4
L(x 4) = 00	L*(X]) + Ru =	0+11 = 11	min{oo, 11} = 11
L(xs) = 00	L*(x{) + R]5 =	0 + 3 = 3	min{oo, 3} = 3

Вершинам х₂, х^ Х5 присвоим новые временные метки, вычисленные в табл.

6. а: Z/(x₂) ⁼ 4, L{x4) =11, L(xs) — 3; метка вершины Х3 осталась без изменения

L{x3) — оо. Занесем новые метки и метку вершины Х3 в первый столбец табл. 4. Обновленные метки выделим.

с) Из всех имеющихся временных меток в столбце 1 (табл. 4) выберем наимень­шую и сделаем ее постоянной для своей вершины: min{4, оо, 11,3} =3. Эта метка соответствует вершине х$. Отметим ее звездочкой в столбце 1 L*(x$) = 3.

Табл. 4

	0	1	2	3	4
XI	0*
х2	00	4
*3	00	00
х4	00	11
*5	00	3*

Шаг 2

а) Определим множество вершин графа, смежных с вершиной Х5, не имеющих еще постоянных меток (рис. 1, табл. 2):

S(x₅)= {Х₂,Х₃,Х₄}.

в) Для каждой вершины, принадлежащей множеству S(x$), вычислим новые вре­менные метки L(xj), равные min{L^CT(xj), L*(x5) + R5_;}, где L^CT(xj) - старая вре­менная метка вершины Xj, L *(*5) ⁼ 3 - постоянная метка вершины Х5 , R- вес ребра (Х5, х_;) (см. табл. 4-а).

= 3 Табл. 4-а

Lato)	L *(*5) + Rsi		min{ LCT(Xi), L*(xs) + R5i}
L(x 2) = 4	L*(x 5) + R52 =	3 + 6 = 9	min{4, 9} =4
Цх3) = оо	^*(*5) + ^53 =	3 + 5 = 8	min{oo, 8} = 8
Цх4) = 11	L *(*5) + ^54 =	3+9 = 12	min{l 1, 12} = 11

Вершине х₃ присвоим новую временную метку, которую вычислили в табл.

35. а: Цх₃) = 8; метки вершин х₂, х₄ остаются без изменения, т.е. L(x?) = 4, L(x₄) =11. Занесем их во второй столбец (табл. 5), причем обновленные метки выделим. с) Из всех имеющихся временных меток в столбце 2 табл. 5 выберем наимень­шую и сделаем ее постоянной для своей вершины: min{4, 8, 11} = 8. Эта метка соответствует вершине х₂: £*(х₂) = 4. Отметим ее звездочкой.

Табл. 5

	0	1	2	3	4
X]	0*
x2	00	4	4*
*3	00	00	8
x4	00	11	11
*5	00	3*

Шаг 3

а) Определим множество вершин графа, смежных с вершиной х₂, не имеющих еще постоянных меток (рис. 1, табл. 2):

S(X₂) = {х₃}.

в) Для вершины Хз, принадлежащей множеству £(х₂), вычислим новую времен­ную метку L(x2), равную тт{Х^ст(хз), Z*(x₂) + ^23 }> ^гД^е ^^СТ(^Х2) ~~ старая вре­менная метка вершины х₂, L *(х₂) = 4 - постоянная метка вершины х₂, R23 - вес ребра (х₂, Хз) (см. табл. 5-а).

b\x₂) = 4 Табл. 5-а

LCT(Xi)	L*(x2) + R2i		min{ LCT(Xj), L*(x2) + i?2/}
L(x3) = 8	L *(x2) + /?23 =	4 + 6= 10	min{8, 10} = 8

Метка вершины Х3 остается без изменения, т.е. L(x3) = 8. Занесем ее в тре­тий столбец (табл. 6).

с) Из всех имеющихся временных меток в третьем столбце табл. 5 выберем наи­меньшую и сделаем ее постоянной для своей вершины: min{8, 11} = 8. Эта метка соответствует вершине х₃: £*(х₃) = 8. Отметим ее звездочкой.

Табл. 6

	0	1	2	3	4
X\	0*
x2	00	4	4*
x3	00	00	8	8*
X4	00	11	11	11
x5	00	3*

Шаг 4

а) Определим множество вершин графа, смежных с вершиной Х3, не имеющих еще постоянных меток (рис. 1, табл. 2):

S(X₃) = {Х₄}.

в) Для вершины Х4, принадлежащей множеству 5(хз), вычислим новую времен­ную метку L(x3), равную min{X^CT(x4), L*(x3) + R34}, где Z,^CT(x4) - старая вре­менная метка вершины Х4, L *(хз) = 8 - постоянная метка вершины Х3, R24 - вес ребра (Х3, Х4) (табл. 6-а).

L(x₃) = 8 Табл. 6-а

LCT(x,)	L*(x3)+R3i		min{ Lc'(Xi), L*(x3) + R3i}
ICT(x4) = 11	L*(x3) + RM =	8 + 2=10	min{l 1, 10} = 10

Вершине Х4 присвоим новую временную метку, т.е. L(x4) = 10. Занесем ее в четвертый столбец (табл. 7).

с) В четвертом столбце табл. 6 одна временная метка. Сделаем ее постоянной. Эта метка соответствует вершине х₄: L*(x₄) = 10. Отметим ее звездочкой.

Табл. 7

	0	1	2	3	4
XI	0*
х2	сю	4	4*
х3	00	00	8	8*
х4	00	11	11	11	10*
Х5	оо	3*

Процесс расстановки меток закончен. Значения их дают кратчайшие рас­стояния от исходной вершины Х] до всех остальных:

L(xt) = 4, L(x3) = 8, Цх₄) = 10, L(x₅) = 3.

На рисунке 2 в квадратных скобках укажем найденные кратчайшие рас­стояния от вершины X] до всех остальных, т.е. взвесим вершины исходного графа.

Рис. 2

[3]

36. Определение кратчайших путей г/

Чтобы найти кратчайшие пути от вершины х\ до всех остальных вершин, используем соотношение:

L*(xj) = L\xd + R_ij9

где вершина X/ предшествует вершине X/.

а) Найдем кратчайший путь от вершины х\ до вершины х₄. Для этого определим, из каких вершин можно попасть в вершину х₄ (то есть какие вершины связаны с вершиной х₄ ребром).

Вершина Х4 имеет три смежные вершины: х_ь х₃, х₅: S(x_b х₃, х₅). Определим, какая из этих вершин удовлетворяет соотношению (4).

I*(x₄) = L*(Xi) + R_i4. (4)

L*(x₄) = 10

L*(x\) = 0 Ru=U L*(x₄) ФЬ*{х\) + R\₄ - 0+11 = 11 L*(x₃) = 8 R₃₄ = 2 Z,*(x₄) = L*(*₃) + /?34= 8+ 2 = 10 I*(x₅) = 3 R₅₄ = 9 L*(x₄) # L*(x₅) + Л₅4 = 3+ 9 = 12

Как видно, только вершина Х3 удовлетворяет соотношению (4). Следова­тельно, в кратчайшем пути вершине Х4 предшествует вершина (Рис. 2). Выде­лим на графе ребро Х3, Х4.

Ь) Определим, какая вершина предшествует вершине Х3 в кратчайшем пути. Вер­шина хз имеет две смежные вершины: Х2, Х5 (вершина Х4 уже вошла в искомый путь и поэтому не рассматривается): S(x2, Х5). Определим, какая из этих вершин удовлетворяет соотношению (4).

L*(x₃) = 8,

L*(х₂) = 4 ^23 = 6 L*(xj) фЬ*(х₂) + Ri3 ⁼ 4 + 6 =10,

L*(х₅) = 3 R₅₃ = 5 L*(xt) - L*(x₅) + Rs3= 3 + 5=8.

Как видно, соотношению (4) удовлетворяет вершина Х5. Следовательно, в кратчайшем пути вершине Х3 предшествует вершина Х5 (рис. 3). Выделим на гра­фе ребро Х5, Х3.

Рис. 3

с) Определим, какая вершина предшествует вершине Х5 в кратчайшем пути. Вер­шина х₅ имеет смежные вершины: X] и Х2 (ещё не вошедшие в искомый путь): S(X\, Х2). Определим, какая из этих вершин удовлетворяет соотношению (4).

L*(x₅) = 3,

L*(jci) = 0 R\s=3 L*(x₅) = L*(x\) + R\s = 0 + 3 = 3,

L*(x₂) = 4 R₂₅ = 6 L*(x₅) Ф L*(x₂) + R₂₅ = 4 + 6=10.

Как видно, соотношению (4) удовлетворяет только вершина х\. Следова­тельно, в кратчайшем пути вершине предшествует вершина х\, которая является исходной (рис. 4). Выделим на графе ребро Х\, х$.

[0]

[41 ₆ [8]

Рис. 4

м) [10]

[3]

Таким образом, минимальный путь от вершины Х\ до вершины лс₅ проходит по вершинам Jti, Х$, ДС3, Х4 и длина этого пути равна 10.

Очевидно, что каждый из путей из вершины X] до любой вершины, входя­щей в построенный кратчайший путь (от вершины X] в вершину Х4), тоже будет оптимальным.

Найдем кратчайший путь от вершины Х\ до вершины х₂.

а) Вершина х₂ имеет смежные вершины: S(jc_b х₃, х₅). Определим, какая из этих вершин удовлетворяет соотношению (4).

L*(x₂) = 4,

L*(JC!) = 0 R\2 =4 L*(x₂) = L*{x_x) + R_X2 = 0 + 4 = 4, L*(x₃) = 8 R₃₂ = 6 L*(x₂) Ф L*(x₃) + Л32 = 8 + 6 = 14, L *(x₅) = 3 R₅₂ = 6 L *(x₇) Ф L *(x₄) + R₅₂ =3 + 6 = 9.

Как видно, соотношению (4) удовлетворяет только вершина х\. Следова­тельно, в кратчайшем пути вершине х₂ предшествует вершина х\. (см. рис. 5).

Таким образом, минимальный путь от вершины Xi до вершины х₂ проходит по ребру (л-_ь х₂) и длина его равна 4 (весу ребра).