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

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

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

Рис. 1

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

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

						табл. 3
		0	1	2	3		4		5
х1		0*
х2		0
х3		0
х4		0
х5		0
х6		0

Предварительно всем вершинам графа, кроме вершины х_ь присвоим вре­менные метки, равные бесконечности: L(x₂) = L(х₃) = L(х₄) = L(х₅) =L(x6)= оо, а вершине Х1присвоим постоянную метку L*(x1)= 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-а

L(Xj)	L*(xi)+R1j		min{LCT(xj), ( L*(x1) +R1j}
L(x2) = 00	L*(x1) + R12 —	0 + 10 = 10	min{oo, 10} = 10
L(x3) = 00	L*(X]) + R13 =	0+6 = 6	min{oo, 6} = 6
L(x4) =00	L*(x1) + R14 =	0 + 15 = 15	min{oo, 15} = 15
L(x5) =00	L*(x1) + R15 =	0 + 9 = 9	min{oo, 9} = 9
L(x6) =00	L*(x1) + R16 =	0 + 11 = 11	min{oo, 11} = 11

Вершинам х₂, х₃ х₄ , х_5, х₆ присвоим новые временные метки, вычисленные в табл.3а

L(x2) ⁼ 10, L{x3) =6, L(x4)=15; L(x5)=9, L(x6)=11, метка вершины Х3 осталась без изменения

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

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

Табл. 4

	0	1	2	3	4	5
х1	0*
х2	00	10
х3	00	6*
х4	00	15
х5	00	9
х6	00	11

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

S(x₆)={Х₂,Х₄,Х_5, Х₆}.

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

Табл. 4-а

L(Xj)	L*(xi)+R3j		min{LCT(xj), ( L*(x1) +R1j}
L(x2) = 10	L*(x3) + R32 —	6+ 10 = 16	min{oo, 10} = 10
L(x4) =15	L*(x3) + R34 =	6 + 15 = 21	min{oo, 15} = 15
L(x5) =9	L*(x3) + R35 =	6 + 18 = 24	min{oo, 9} = 9
L(x6) =11	L*(x3) + R36 =	6 + 12 = 18	min{oo, 11} = 11

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

L(х₃) = 9; метки вершин х₃, х₅ остаются без изменения, т.е. L(x3) = 6, L(x₅) =9. Занесем их во второй столбец (табл. 5), причем обновленные метки выделим. с) Из всех имеющихся временных меток в столбце 2 табл. 5 выберем наимень­шую и сделаем ее постоянной для своей вершины: min{10, 15,9,11} = 9. Эта метка соответствует вершине L(х₅) = 9. Отметим ее звездочкой.

Табл. 5

	0	1	2	3	4	5
х1	0*
х2	0	10	10
х3	0	6*
х4	0	15	15
х5	0	9	9*
х6	0	11	11

Шаг 3

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

S(X₂) = {х₃}.

в) Для вершины х₂, принадлежащей множеству S(х₃), вычислим новую времен­ную метку L(x3), равную min{L^ст(х2), L*(x₅) + R_5j } где L^СТ(^Х5) ~~ старая вре­менная метка вершины х₅, L*(х₅) = 9 - постоянная метка вершины х₂, (см. табл. 5-а).

L(x₅)= 9 Табл. 5-а

LCT(Xi)	L*(xi)+R5j		min{LCT(xj), ( L*(x1) +R1j}
L(x2) = 10	L*(x5) + R52 =	9+ 10 = 19	min{oo, 10} = 10
L(x4) =15	L*(x5) + R54 =	9 + 15 = 24	min{oo, 15} = 15
L(x6) =11	L*(x5) + R56 =	9+ 11 =20	min{oo, 11} = 11

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

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

Табл. 6

	0	1	2	3	4	5
х1	0*
х2	0	10	10	10*
х3	0	6*
х4	0	15	15	15
х5	0	9	9*
х6	0	11	11	11

Шаг 4

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

S(X₂) = {Х_4, Х₆}.

в) Для вершины Х6, принадлежащей множеству S(х2), вычислим новую времен­ную метку L(x2), равную min{X^CT(x4), L*(x2) + R24}, где L^CT(x4) - старая вре­менная метка вершины Х2, L*(х2) = 10 - постоянная метка вершины Х2,

L(x₂) = 10 Табл. 6-а

LCT(Xi)	L*(xi)+R2j		min{LCT(xj), ( L*(x1) +R1j}
L(x4) =15	L*(x2) + R24 =	10 + 15 = 25	min{oo, 15} = 15
L(x6) =11	L*(x2) + R26 =	10+ 12=22	min{oo, 11} = 11

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

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

Табл. 7

	0	1	2	3	4	5
х1	0*
х2	0	10	10	10*
х3	0	6*
х4	0	15	15	15	15
х5	0	9	9*
х6	0	11	11	11	11*

Шаг 5

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

S(X₆) = {Х₄}.

в) Для вершины Х6, принадлежащей множеству S(х6), вычислим новую времен­ную метку L(x2), равную min{X^CT(x4), L*(x2) + R24}, где L^CT(x4) - старая вре­менная метка вершины Х2, L*(х2) = 10 - постоянная метка вершины Х2,

L(x₄) = 15 Табл. 7-а

LCT(Xi)	L*(xi)+R4j		min{LCT(xj), ( L*(x1) +R1j}
L(x4) =15	L*(x4) + R45 =	15 + 11 = 26	min{oo, 15} = 15

Вершине Х5 присвоим новую временную метку, т.е. L(x5) = 15. Занесем ее в четвертый столбец (табл. 8).

	0	1	2	3	4	5
х1	0*
х2	0	10	10	10*
х3	0	6*
х4	0	15	15	15	15	15*
х5	0	9	9*
х6	0	11	11	11	11*

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

L(x2) = 10, L(x3) = 6, L(х₄) = 15, L(x₅) = 9, L(x₆)=11.

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

Рис. 2