Лабораторная работа №25. Понятие графа. Алгоритмы поиска кратчайших путей

Рис. 2. Демонстрация алгоритма Флойда
//Описание функции алгоритма Флойда
void Floyd(int n, int **Graph, int **ShortestPath){
int i, j, k;
int Max_Sum = 0;
for ( i = 0 ; i < n ; i++ )
for ( j = 0 ; j < n ; j++ )
Max_Sum += ShortestPath[i][j];
for ( i = 0 ; i < n ; i++ )
for ( j = 0 ; j < n ; j++ )
if ( ShortestPath[i][j] == 0 && i != j )
ShortestPath[i][j] = Max_Sum;
for ( k = 0 ; k < n; k++ )
for ( i = 0 ; i < n; i++ )
for ( j = 0 ; j < n ; j++ )
if ((ShortestPath[i][k] + ShortestPath[k][j]) <
ShortestPath[i][j])
ShortestPath[i][j] = ShortestPath[i][k] +
ShortestPath[k][j];
}
Заметим, что если граф неориентированный, то все матрицы, получаемые в результате преобразований симметричны и, следовательно, достаточно вычислять только элементы, расположенные выше главной диагонали.
Если граф представлен матрицей смежности, то время выполнения этого алгоритма имеет порядок O(n³), поскольку в нем присутствуют вложенные друг в друга три цикла.
Переборные алгоритмы
Переборные алгоритмы по сути своей являются алгоритмами поиска, как правило, поиска оптимального решения. При этом решение конструируется постепенно. В этом случае обычно говорят о переборе вершин дерева вариантов. Вершинами такого графа будут промежуточные или конечные варианты, а ребра будут указывать пути конструирования вариантов.
Рассмотрим переборные алгоритмы, основанные на методах поиска в графе, на примере задачи нахождения кратчайшего пути в лабиринте.
Постановка задачи.
Лабиринт, состоящий из проходимых и непроходимых клеток, задан матрицей A размером mxn. Элемент матрицы A[i,j]=0, если клетка (i,j) проходима. В противном случае  .
Требуется найти длину кратчайшего пути из клетки (1, 1) в клетку (m, n).
Фактически дана матрица смежности (только в ней нули заменены бесконечностями, а единицы – нулями). Лабиринт представляет собой граф.
Вершинами дерева вариантов в данной задаче являются пути, начинающиеся в клетке (1, 1). Ребра – показывают ход конструирования этих путей и соединяют два пути длины k и k+1, где второй путь получается из первого добавлением к пути еще одного хода.
Перебор с возвратом
Данный метод основан на методе поиска в глубину. Перебор с возвратом считают методом проб и ошибок ("попробуем сходить в эту сторону: не получится – вернемся и попробуем в другую"). Так как перебор вариантов осуществляется методом поиска в глубину, то целесообразно во время работы алгоритма хранить текущий путь в дереве. Этот путь представляет собой стек Way.
Также необходим массив Dist, размерность которого соответствует количеству вершин графа, хранящий для каждой вершины расстояние от нее до исходной вершины.
Пусть текущей является некоторая клетка (в начале работы алгоритма – клетка (1, 1) ). Если для текущей клетки есть клетка-сосед Neighbor, отсутствующая в Way, в которую на этом пути еще не ходили, то добавляем Neighbor в Way и текущей клетке присваиваем Neighbor, иначе извлечь из Way.
Приведенное выше описание дает четко понять, почему этот метод называется перебором с возвратом. Возврату здесь соответствует операция "извлечь из Way ", которая уменьшает длину Way на 1.
Перебор заканчивается, когда Way пуст и делается попытка возврата назад. В этой ситуации возвращаться уже некуда (рис. 3).
Way является текущим путем, но в процессе работы необходимо хранить и оптимальный путь OptimalWay.
Усовершенствование алгоритма можно произвести следующим образом: не позволять, чтобы длина Way была больше или равна длине OptimalWay. В этом случае, если и будет найден какой-то вариант, он заведомо не будет оптимальным. Такое усовершенствование в общем случае означает, что как только текущий путь станет заведомо неоптимальным, надо вернуться назад. Данное улучшение алгоритма позволяет во многих случаях сильно сократить перебор.