Практикум по курсу "Алгоритмизация и программирование". Часть 2. Андрианова А.А - 120 стр.

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова .
Таблица 3. Поиск кратчайшего пути алгоритмом Дейкстра. Продолжение.
№
Действия с
комментариями
Зафиксир.
вершина
Состояние
массива по-
меток X
Состояние
массива
длин T
Состояние
массива
путей H
5
Находим в массиве T
минимальный элемент,
среди тех, которые со-
ответствуют непомечен-
ным вершинам
(Т[4]=8). Помечаем
вершину 4 и фиксируем
ее.
4
{1, 1, 0,
1, 0, 0}
{0, 7, 9,
8, ∝, 13}
{0, 1, 2,
1, ∝, 2}
6
Для вершины 4 смеж-
ной непомеченной вер-
шиной является верши-
на 5. Меняем T[5] и
H[5].
4
{1, 1, 0,
1, 0, 0}
{0, 7, 9,
8, 10, 13}
{0, 1, 2,
1, 4, 2}
7
Находим в массиве T
минимальный элемент,
среди соответствующих
непомеченным верши-
нам (Т[3]=9). Помеча-
ем вершину 3 и фикси-
руем ее.
3
{1, 1, 1,
1, 0, 0}
{0, 7, 9,
8, 10, 13}
{0, 1, 2,
1, 4, 2}
8
Для вершины 3 смеж-
ной непомеченной вер-
шиной является верши-
на 6. Меняем элементы
T[6] и H[6].
3
{1, 1, 1,
1, 0, 0}
{0, 7, 9,
8, 10, 12}
{0, 1, 2,
1, 4, 3}
9
Находим в массиве T
минимальный элемент,
среди тех, которые со-
ответствуют непомечен-
ным вершинам
(Т[5]=10). Помечаем
вершину 5 и фиксируем
ее.
5
{1, 1, 1,
1, 1, 0}
{0, 7, 9,
8, 10, 12}
{0, 1, 2,
1, 4, 3}
10 Для вершины 5 смежной непомеченной вершиной является вершина 6. Ми-
120
А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова                                 .


          Таблица 3. Поиск кратчайшего пути алгоритмом Дейкстра. Продолжение.

                                   Зафиксир.      Состояние     Состояние    Состояние
             Действия с
№                                                 массива по-    массива      массива
           комментариями            вершина        меток X       длин T       путей H

      Находим в массиве T
      минимальный элемент,
      среди тех, которые со-
      ответствуют непомечен-                       {1, 1, 0,     {0, 7, 9,    {0, 1, 2,
 5                                      4
      ным          вершинам                         1, 0, 0}    8, ∝, 13}     1, ∝, 2}
      (Т[4]=8).    Помечаем
      вершину 4 и фиксируем
      ее.

      Для вершины 4 смеж-
      ной непомеченной вер-                                      {0, 7, 9,
      шиной является верши-                        {1, 1, 0,                  {0, 1, 2,
6                                       4
      на 5. Меняем T[5] и                          1, 0, 0}     8, 10, 13}    1, 4, 2}
      H[5].

      Находим в массиве T
      минимальный элемент,
      среди соответствующих                                      {0, 7, 9,
                                                   {1, 1, 1,                  {0, 1, 2,
 7    непомеченным верши-               3
                                                   1, 0, 0}     8, 10, 13}    1, 4, 2}
      нам (Т[3]=9). Помеча-
      ем вершину 3 и фикси-
      руем ее.

      Для вершины 3 смеж-
      ной непомеченной вер-                                      {0, 7, 9,
                                                   {1, 1, 1,                  {0, 1, 2,
 8    шиной является верши-             3
                                                   1, 0, 0}     8, 10, 12}    1, 4, 3}
      на 6. Меняем элементы
      T[6] и H[6].

      Находим в массиве T
      минимальный элемент,
      среди тех, которые со-
      ответствуют непомечен-                       {1, 1, 1,     {0, 7, 9,    {0, 1, 2,
 9                                      5
      ным          вершинам                        1, 1, 0}     8, 10, 12}    1, 4, 3}
      (Т[5]=10). Помечаем
      вершину 5 и фиксируем
      ее.

10    Для вершины 5 смежной непомеченной вершиной является вершина 6. Ми-
                                            120

Страницы