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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

. Практикум по курсу «Алгоритмизация и программирование». Часть 2
printf("%d<-",t);
while(H[i]!=0)
{
printf("%d<-",H[i]);
i=H[i]-1;
}
. . .
Рассмотрим процесс печати кратчайшего пути для нашего примера. Ре-
зультатом решения задачи является массив H[]={0, 1, 2, 1, 4, 3}. Находясь в
конечной вершине 6, получаем номер предыдущей вершины на пути H[6]=3.
Далее вершине 3 предшествует H[3]=2, второй – H[2]=1. Таким образом,
кратчайший путь из вершины 1 в вершину 6 : 1->2->3->6.
Задача 5. Дан взвешенный граф в виде матрицы смежности. Найти крат-
чайшие пути между всеми парами вершин.
Для решения этой задачи часто используется алгоритм Флойда (1962 г.).
Результатом работы алгоритма являются две матрицы: H и T размера n×n,
где n – количество вершин графа. Элемент матрицы T[i][j] соответствует
кратчайшему расстоянию между вершинами i и j. В матрице H хранится ин-
формация о кратчайших путях:
k, если k – номер первой вершины, в которую необходимо
перейти, двигаясь из i в j
H[i][j]=
0, если из вершины i в вершину j нет пути.
Сначала осуществляется начальная инициализация матриц H и T. Матри-
ца T совпадает с матрицей смежности, т.е. фиксируются пути, состоящие из
одного ребра. В матрице H для каждой пары смежных вершин в качестве на-
чального значения берется номер конечной вершины ребра.
Для любой пары вершин j и k осуществляется попытка включить в путь
новую вершину i. Это происходит при выполнении следующих условий:
1) вершина i не является концом рассматриваемого пути, т.е. не совпада-
ет с j или с k;
2) существует путь из j в i и из i в k;
3) длина полученного пути через вершину i меньше, чем прежняя длина.
Если все эти условия выполнены, то меняется длина кратчайшего пути в
матрице T, и первой вершиной на пути из j в k становится первая вершина на
123
            .        Практикум по курсу «Алгоритмизация и программирование». Часть 2
    printf("%d<-",t);
    while(H[i]!=0)
    {
          printf("%d<-",H[i]);
          i=H[i]-1;
    }
    . . .

    Рассмотрим процесс печати кратчайшего пути для нашего примера. Ре-
зультатом решения задачи является массив H[]={0, 1, 2, 1, 4, 3}. Находясь в
конечной вершине 6, получаем номер предыдущей вершины на пути H[6]=3.
Далее вершине 3 предшествует H[3]=2, второй – H[2]=1. Таким образом,
кратчайший путь из вершины 1 в вершину 6 : 1->2->3->6.
    Задача 5. Дан взвешенный граф в виде матрицы смежности. Найти крат-
чайшие пути между всеми парами вершин.
    Для решения этой задачи часто используется алгоритм Флойда (1962 г.).
    Результатом работы алгоритма являются две матрицы: H и T размера n×n,
где n – количество вершин графа. Элемент матрицы T[i][j] соответствует
кратчайшему расстоянию между вершинами i и j. В матрице H хранится ин-
формация о кратчайших путях:

                 k, если k – номер первой вершины, в которую необходимо
                 перейти, двигаясь из i в j
H[i][j]=
                 0, если из вершины i в вершину j нет пути.


     Сначала осуществляется начальная инициализация матриц H и T. Матри-
ца T совпадает с матрицей смежности, т.е. фиксируются пути, состоящие из
одного ребра. В матрице H для каждой пары смежных вершин в качестве на-
чального значения берется номер конечной вершины ребра.
     Для любой пары вершин j и k осуществляется попытка включить в путь
новую вершину i. Это происходит при выполнении следующих условий:
     1) вершина i не является концом рассматриваемого пути, т.е. не совпада-
ет с j или с k;
     2) существует путь из j в i и из i в k;
     3) длина полученного пути через вершину i меньше, чем прежняя длина.
     Если все эти условия выполнены, то меняется длина кратчайшего пути в
матрице T, и первой вершиной на пути из j в k становится первая вершина на

                                      123

Страницы