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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

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




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

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

    Фиксируем начальную                     {1, 0, 0,     {1, 0, 0,     {0,∝, ∝,
1                                1
    вершину пути                             0, 0, 0}      0, 0, 0}     ∝, ∝, ∝}

    Для вершины 1 смеж-
    ными непомеченными
    вершинами     являются
    вершины 2, 3, 4. Меня-
    ем для них элементы                                   {0, 7, 11,    {0, 1, 1,
                                            {1, 0, 0,
2   массивов T и H, т.е.         1
    Т[2], Н[2], T[3],                        0, 0, 0}     8, ∝, ∝}      1, ∝, ∝}
    H[3], T[4], H[4] (в Т
    заносим длину ребра, в
    Н – номер зафикс. вер-
    шины).

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

    Для вершины 2 смеж-
    ными непомеченными
    вершинами    являются                   {1, 1, 0,     {0, 7, 9,     {0, 1, 2,
4                                2
    вершины 3, 6. Меняем                     0, 0, 0}     8, ∝, 13}     1, ∝, 2}
    для них элементы мас-
    сивов T и H.




                                     119

Страницы