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

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

L*(xj) = L*(xi) + R_ij

где вершина X_i предшествует вершине X_j.

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

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

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

L*(x₄) = 15

L*(x1)=0	R14=15	L*(x4)=L*(x1)+R14=0+15=15
L*(x2)=10	R24=12	L*(x4)≠L*(x2)+R24=10+12=22
L*(x3)=6	R34=15	L*(x4)≠L*(x3)+R34=6+15=21
L*(x5)=9	R54=21	L*(x4)≠L*(x5)+R54=9+21=30
L*(x6)=11	R64=17	L*(x4)≠L*(x6)+R64=11+17=28

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

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

L*(x₆) =11,

L*(x1)=0	R16=11	L*(x6)=L*(x0)+R16=0+11=11
L*(x2)=10	R26=14	L*(x6)≠L*(x2)+R26=10+14=24
L*(x3)=6	R36=12	L*(x6)≠L*(x3)+R36=6+12=18
L*(x5)=9	R56=16	L*(x6)≠L*(x5)+R56=9+16=25

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

Рис. 3

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

L*(x₂) = 10,

L*(x1)=0	R12=10	L*(x2)=L*(x0)+R12=0+10=10
L*(x3)=6	R32=10	L*(x2)=L*(x3)+R32=6+10=16
L*(x5)=9	R52=21	L*(x2)=L*(x5)+R52=9+21=30

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

Рис. 4

Таким образом, минимальный путь от вершины Х1 до вершины x₆ проходит по вершинам x_1, x_2, x_4, x₆ и длина этого пути равна 39.

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

Найдем кратчайший путь от вершины x₁ до вершины х₅.

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

L*(x₅) = 9,

L*(x1)=0	R15=9	L*(x5)=L*(x0)+R15=0+9=9
L*(x3)=6	R35=18	L*(x5)=L*(x3)+R35=6+18=24

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

Таким образом, минимальный путь от вершины х₁ до вершины х₃ проходит по ребру (х₁х₃) и длина его равна 6 (весу ребра).