рейтинговая работа. Рейтинговая работа. Кафедра Математика и информатика
 Скачать 0.56 Mb.
|
|
0                 ∞ ∞     ∞        ∞ ∞    Минимальную метку имеет вершина 2. Её соседи (учитываем направление рёбер) – вершины 1, 3; проставляем для них новые метки: для 1: min (∞,0+1) =1 и для 3: min (∞,0+12=12.  12 0 1 ∞ ∞ ∞ ∞ При каждом изменении меток будем выписывать пути от старта, которые реализуют новые метки для вершин:  Все соседние вершины для 2 проверены. Текущее значение для вершины 2 считается окончательным. Исключаем далее эту вершину из рассмотрения (помечаем рамку метки красным цветом) – вершина становится постоянной. Из непостоянных вершин берём вершину с минимальным весом – вершину 1. Соседи этой вершины (кроме вершины 2): 5, 6. Обновляем для них метки аналогично:   12 0 1 ∞ 12 9 ∞ Изменились метки для  , новые пути для них: Все соседние вершины для 1 проверены. Текущее значение для вершины 1 считается окончательным, она становится постоянной. Непостоянная вершина с минимальным весом – вершина 6. У неё соседние вершины: 5, 7 (из непостоянных). Обновляем метки для обеих (для 5-й вершины 9+2<12): 12 0 |