Алгоритмы на графах и их приложения. Дорофеева В.И. - 34 стр.

UptoLike

ВУЗ: 

ОГУ | Орел

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

Рубрика: 

34
Первая итерация.
Первый шаг. Присвоим вершине 1 метку [1,@]. Рассмотрим дуги, нача-
лом которых является вершина 1 – дуги (1,2) и (1,3). Вершины 2 и 3 не помече-
ны, по этому присваиваем им метки, для 2-й – [1,2] и 3-й – [1,6]. Что представ-
ляют из собой метки? Первая цифра – номер вершины, из которой идет ребро,
вторая цифра – численное значение длины пути пройденного по графу до дан-
ной вершины.
Второй шаг. Выберем помеченную, но не просмотренную вершину. Пер-
вой в соответствующей структуре данных записана вершина 2. Рассмотрим ду-
ги, для которых она является началом – дуги (2,4) и (2,5). Вершины 4 и 5 не по-
мечены. Присвоим им метки [2,4] и [2,3]. Итак, на втором шаге вершина 2 про-
смотрена, вершины 3,4,5 помечены, но не просмотрены, остальные вершины не
помечены.
Третий шаг. Выбираем вершину 3. Рассмотрим дугу (3,4). Вершина 4 по-
мечена. Сравниваем, как на данном шаге мы можем пометить данную вершину,
[3,8] из 3-й вершины пройдя 8 единиц пути. Это длиннее чем 4 поэтому остав-
ляем метку без изменения. Переходим к следующей вершине – четвертой, соот-
ветствующая дуга – (4,6). Вершина 6 не помечена. Присваиваем ей метку [4,6].
Далее переходим к следующей вершине. Вершина 5 помечена как [4,6] сравни-
ваем как на данном этапе можно пометить вершину, [5,5] т.е. найден более ко-
роткий путь. Поэтому помечаем вершину заново как [5,5] Мы достигли верши-
1
2
3
5
6
4
[1,@]
[1,6]
[1,2]
[2,4]
[5,5]
[2,3]
2
1
6
2
2
4
2
2
Рисунок 34 
                        [1,2]                                [2,3]
                                            1
                                2                        5


                    2                   2
                                                     4        2
                                                                              [5,5]
        [1,@]
                1                                                         6



                    6                                                 2
                                [1,6]
                                            2
                                3                        4    [2,4]



                                        Рисунок 34
     Первая итерация.
     Первый шаг. Присвоим вершине 1 метку [1,@]. Рассмотрим дуги, нача-
лом которых является вершина 1 – дуги (1,2) и (1,3). Вершины 2 и 3 не помече-
ны, по этому присваиваем им метки, для 2-й – [1,2] и 3-й – [1,6]. Что представ-
ляют из собой метки? Первая цифра – номер вершины, из которой идет ребро,
вторая цифра – численное значение длины пути пройденного по графу до дан-
ной вершины.
      Второй шаг. Выберем помеченную, но не просмотренную вершину. Пер-
вой в соответствующей структуре данных записана вершина 2. Рассмотрим ду-
ги, для которых она является началом – дуги (2,4) и (2,5). Вершины 4 и 5 не по-
мечены. Присвоим им метки [2,4] и [2,3]. Итак, на втором шаге вершина 2 про-
смотрена, вершины 3,4,5 помечены, но не просмотрены, остальные вершины не
помечены.
     Третий шаг. Выбираем вершину 3. Рассмотрим дугу (3,4). Вершина 4 по-
мечена. Сравниваем, как на данном шаге мы можем пометить данную вершину,
[3,8] из 3-й вершины пройдя 8 единиц пути. Это длиннее чем 4 поэтому остав-
ляем метку без изменения. Переходим к следующей вершине – четвертой, соот-
ветствующая дуга – (4,6). Вершина 6 не помечена. Присваиваем ей метку [4,6].
Далее переходим к следующей вершине. Вершина 5 помечена как [4,6] сравни-
ваем как на данном этапе можно пометить вершину, [5,5] т.е. найден более ко-
роткий путь. Поэтому помечаем вершину заново как [5,5] Мы достигли верши-
                                     34

Страницы