Компьютерная математика: Часть 2. Теория графов. Волченская Т.В - 61 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

ПРИМЕР. Рассмотрим граф смешанного типа, изображенный на рис. 28,а,
где каждое неориентированное ребро рассматривается как пара противоположно
направленных дуг равного веса. Матрица весов приведена на рис.28,б. Требуется
найти все кратчайшие пути от вершины х
1
ко всем остальным вершинам.
Постоянные пометки будем помечать знаком "+".
ШАГ 1. Присвоим L(x
1
)=0, L(x
i
)=∞ для всех x
i
, кроме x
1
. Положим р = x
1
.
Первая итерация
ШАГ 2. Найдем прямое отображение для текущей рассматриваемой вершины:
Г(
р)=Г(x
1
)={ x
2
, x
7
, x
8
, x
9
}. Все вершины, входящие в прямое отображение имеют
временные пометки, поэтому пересчитаем их значение:
L(x
2
) = min [ L(x
2
), L(x
1
)+c(x
1
, x
2
) ] = min [ ∞, 0+10 ] =10
L(x
7
) = min [ ∞, 0+3 ] = 3
L(x
8
) = min [ ∞, 0+6 ] = 6
L(x
9
) = min [ ∞, 0+12 ] = 12
ШАГ 3
. На данном шаге итерации имеем следующие временные метки вершин:
L(x
2
) = 10, L(x
3
) = ∞,
L(x
7
) = 3, L(x
4
) = ∞,
L(x
8
) = 6, L(x
5
) = ∞,
L(x
9
) = 12, L(x
6
) = ∞.
Очевидно, что минимальную метку, равную 3, имеет вершина x
7
.
x
1
x
8
x
5
x
9
x
7
x
8
x
2
x
3
x
4
x
6
а)
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
x
9
x
1
10 3 6 12
x
2
10 18 2 13
x
3
18 25 20 7
x
4
25 5 16 4
C=
x
5
5 10
x
6
20 10 14 15 9
x
7
2 4 14 24
x
8
6 23 15 5
x
9
12 13 9 24 5
б)
Рис. 28. Пример поиска кратчайшего пути:
а) - граф;
б) - матрица весов дуг 
        ПРИМЕР. Рассмотрим граф смешанного типа, изображенный на рис. 28,а,
где каждое неориентированное ребро рассматривается как пара противоположно
направленных дуг равного веса. Матрица весов приведена на рис.28,б. Требуется
найти все кратчайшие пути от вершины х1 ко всем остальным вершинам.
        Постоянные пометки будем помечать знаком "+".

         x2                        x3
                                                         x1 x2 x3 x4 x5 x6 x7   x8 x9
                                                     x1    10              3    6 12
                                                     x2 10    18           2       13
x1                 x7
                                         x4          x3    18    25     20         7
                                                     x4       25    5   16 4
                                                  C= x5          5      10
              x9              x6                     x6       20    10     14   15 9
                                                     x7    2     4      14         24
        x8                         x5                x8 6           23  15         5
                                                     x9 12 13           9 24    5
                        а)                                          б)



     Рис. 28. Пример поиска кратчайшего пути:
           а) - граф;
           б) - матрица весов дуг


ШАГ 1. Присвоим L(x1)=0, L(xi)=∞ для всех xi, кроме x1. Положим р = x1.
        Первая итерация
ШАГ 2. Найдем прямое отображение для текущей рассматриваемой вершины:
Г(р)=Г(x1)={ x2, x7, x8, x9 }. Все вершины, входящие в прямое отображение имеют
временные пометки, поэтому пересчитаем их значение:
        L(x2) = min [ L(x2), L(x1)+c(x1, x2) ] = min [ ∞, 0+10 ] =10
        L(x7) = min [ ∞, 0+3 ] = 3
        L(x8) = min [ ∞, 0+6 ] = 6
        L(x9) = min [ ∞, 0+12 ] = 12
ШАГ 3. На данном шаге итерации имеем следующие временные метки вершин:
        L(x2) = 10,      L(x3) = ∞,
        L(x7) = 3,       L(x4) = ∞,
        L(x8) = 6,       L(x5) = ∞,
         L(x9) = 12, L(x6) = ∞.
Очевидно, что минимальную метку, равную 3, имеет вершина x7.

Страницы