Алгоритмы на графах. Алгоритмы нахождения кратчайшего пути

Цель лекции: изучить основные алгоритмы поиска кратчайшего пути и научиться решать задачи поиска кратчайшего пути на основе алгоритмов Дейкстры, Флойда и переборных алгоритмов.

Нахождение кратчайшего пути на сегодняшний день является жизненно необходимой задачей и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (например, кратчайший путь от дома до университета), в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутации информационного пакета в сетях и т.п.

Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом. Поиск кратчайшего пути ведется между двумя заданными вершинами в графе. Результатом является путь, то есть последовательность вершин и ребер, инцидентных двум соседним вершинам, и его длина.

Рассмотрим три наиболее эффективных алгоритма нахождения кратчайшего пути:

Указанные алгоритмы легко выполняются при малом количестве вершин в графе. При увеличении их количества задача поиска кратчайшего пути усложняется.

Алгоритм Дейкстры

Данный алгоритм является алгоритмом на графах, который изобретен нидерландским ученым Э. Дейкстрой в 1959 году. Алгоритм находит кратчайшее расстояние от одной из вершин графа до всех остальных и работает только для графов без ребер отрицательного веса.

Каждой вершине приписывается вес – это вес пути от начальной вершины до данной. Также каждая вершина может быть выделена. Если вершина выделена, то путь от нее до начальной вершины кратчайший, если нет – то временный. Обходя граф, алгоритм считает для каждой вершины маршрут, и, если он оказывается кратчайшим, выделяет вершину. Весом данной вершины становится вес пути. Для всех соседей данной вершины алгоритм также рассчитывает вес, при этом ни при каких условиях не выделяя их. Алгоритм заканчивает свою работу, дойдя до конечной вершины, и весом кратчайшего пути становится вес конечной вершины.

Алгоритм Дейкстры

Шаг 1. Всем вершинам, за исключением первой, присваивается вес равный бесконечности, а первой вершине – 0.

Шаг 2. Все вершины не выделены.

Шаг 3. Первая вершина объявляется текущей.

Шаг 4. Вес всех невыделенных вершин пересчитывается по формуле: вес невыделенной вершины есть минимальное число из старого веса данной вершины, суммы веса текущей вершины и веса ребра, соединяющего текущую вершину с невыделенной.

Шаг 5. Среди невыделенных вершин ищется вершина с минимальным весом. Если таковая не найдена, то есть вес всех вершин равен бесконечности, то маршрут не существует. Следовательно, выход. Иначе, текущей становится найденная вершина. Она же выделяется.

Шаг 6. Если текущей вершиной оказывается конечная, то путь найден, и его вес есть вес конечной вершины.

Шаг 7. Переход на шаг 4.

В программной реализации алгоритма Дейкстры построим множество S вершин, для которых кратчайшие пути от начальной вершины уже известны. На каждом шаге к множеству S добавляется та из оставшихся вершин, расстояние до которой от начальной вершины меньше, чем для других оставшихся вершин. При этом будем использовать массив D, в который записываются длины кратчайших путей для каждой вершины. Когда множество S будет содержать все вершины графа, тогда массив D будет содержать длины кратчайших путей от начальной вершины к каждой вершине.

Помимо указанных массивов будем использовать матрицу длин C, где элемент C[i,j] –длина ребра (i,j), если ребра нет, то ее длина полагается равной бесконечности, то есть больше любой фактической длины ребер. Фактически матрица C представляет собой матрицу смежности, в которой все нулевые элементы заменены на бесконечность.

Для определения самого кратчайшего пути введем массив ).

//Описание функции алгоритма Дейкстры
void Dijkstra(int n, int **Graph, int Node){
  bool *S = new bool[n];
  int *D = new int[n];
  int *P = new int[n];
  int i, j;
  int Max_Sum = 0;
  for (i = 0 ; i < n ; i++)
    for (j = 0 ; j < n ; j++)
      Max_Sum += Graph[i][j];
  for (i = 0 ; i < n ; i++)
    for (j = 0 ; j < n ; j++)
      if (Graph[i][j] == 0) 
        Graph[i][j] = Max_Sum;
  for (i = 0 ; i < n ; i++){
    S[i] = false;
    P[i] = Node;
    D[i] = Graph[Node][i];
  }
  S[Node] = true;
  P[Node] = -1;
  for ( i = 0 ; i < n - 1 ; i++ ){
    int w = 0;
    for ( j = 1 ; j < n ; j++ ){
      if (!S[w]){
        if (!S[j]  D[j] <= D[w])
          w = j;
      }
      else w++;
    }
    S[w] = true;
    for ( j = 1 ; j < n ; j++ )
      if (!S[j])
        if (D[w] + Graph[w][j] < D[j]){
          D[j] = D[w] + Graph[w][j];
          P[j] = w;
        }
  }
  for ( i = 0 ; i < n ; i++ )
    printf("%5d",D[i]);
  cout << endl;
  for ( i = 0 ; i < n ; i++ )
    printf("%5d",P[i]+1);
  cout << endl;
  delete [] P;
  delete [] D;
  delete [] S;
}

Сложность алгоритма Дейкстры зависит от способа нахождения вершины, а также способа хранения множества непосещенных вершин и способа обновления длин.

Если для представления графа использовать матрицу смежности, то время выполнения этого алгоритма имеет порядок O(n2), где n – количество вершин графа.

Алгоритм Флойда

Рассматриваемый алгоритм иногда называют алгоритмом Флойда-Уоршелла. Алгоритм Флойда-Уоршелла является алгоритмом на графах, который разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом. Он служит для нахождения кратчайших путей между всеми парами вершин графа.

Метод Флойда непосредственно основывается на том факте, что в графе с положительными весами ребер всякий неэлементарный (содержащий более 1 ребра) кратчайший путь состоит из других кратчайших путей.

Этот алгоритм более общий по сравнению с алгоритмом Дейкстры, так как он находит кратчайшие пути между любыми двумя вершинами графа.

В алгоритме Флойда используется матрица A размером nxn, в которой вычисляются длины кратчайших путей. Элемент A[i,j] равен расстоянию от вершины i к вершине j, которое имеет конечное значение, если существует ребро (i,j), и равен бесконечности в противном случае.

Алгоритм Флойда

Основная идея алгоритма. Пусть есть три вершины i, j, k и заданы расстояния между ними. Если выполняется неравенство A[i,k]+A[k,j]<A[i,j], то целесообразно заменить путь i->j путем i->k->j. Такая замена выполняется систематически в процессе выполнения данного алгоритма.

Шаг 0. Определяем начальную матрицу расстояния A0 и матрицу последовательности вершин S0. Каждый диагональный элемент обеих матриц равен 0, таким образом, показывая, что эти элементы в вычислениях не участвуют. Полагаем k = 1.

Основной шаг k. Задаем строку k и столбец k как ведущую строку и ведущий столбец. Рассматриваем возможность применения замены описанной выше, ко всем элементам A[i,j] матрицы Ak-1. Если выполняется неравенство $$A[i,k]+A[k,j]<A[i,j], (i\ne k, j\ne k, i\ne j)$$, тогда выполняем следующие действия:

Таким образом, алгоритм Флойда делает ).

//Описание функции алгоритма Флойда
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(n3), поскольку в нем присутствуют вложенные друг в друга три цикла.

Переборные алгоритмы

Переборные алгоритмы по сути своей являются алгоритмами поиска, как правило, поиска оптимального решения. При этом решение конструируется постепенно. В этом случае обычно говорят о переборе вершин дерева вариантов. Вершинами такого графа будут промежуточные или конечные варианты, а ребра будут указывать пути конструирования вариантов.

Рассмотрим переборные алгоритмы, основанные на методах поиска в графе, на примере задачи нахождения кратчайшего пути в лабиринте.

Постановка задачи.

Лабиринт, состоящий из проходимых и непроходимых клеток, задан матрицей A размером mxn. Элемент матрицы A[i,j]=0, если клетка (i,j) проходима. В противном случае $$A[i,j]=\infty$$.

Требуется найти длину кратчайшего пути из клетки (1, 1) в клетку (m, n).

Фактически дана матрица смежности (только в ней нули заменены бесконечностями, а единицы – нулями). Лабиринт представляет собой граф.

Вершинами дерева вариантов в данной задаче являются пути, начинающиеся в клетке (1, 1). Ребра – показывают ход конструирования этих путей и соединяют два пути длины k и k+1, где второй путь получается из первого добавлением к пути еще одного хода.

Перебор с возвратом

Данный метод основан на методе поиска в глубину. Перебор с возвратом считают методом проб и ошибок ("попробуем сходить в эту сторону: не получится – вернемся и попробуем в другую"). Так как перебор вариантов осуществляется методом поиска в глубину, то целесообразно во время работы алгоритма хранить текущий путь в дереве. Этот путь представляет собой стек Way.

Также необходим массив Dist, размерность которого соответствует количеству вершин графа, хранящий для каждой вершины расстояние от нее до исходной вершины.

Пусть текущей является некоторая клетка (в начале работы алгоритма – клетка (1, 1) ). Если для текущей клетки есть клетка-сосед Neighbor, отсутствующая в Way, в которую на этом пути еще не ходили, то добавляем Neighbor в Way и текущей клетке присваиваем Neighbor, иначе извлечь из Way.

Приведенное выше описание дает четко понять, почему этот метод называется перебором с возвратом. Возврату здесь соответствует операция "извлечь из Way ", которая уменьшает длину Way на 1.

Перебор заканчивается, когда Way пуст и делается попытка возврата назад. В этой ситуации возвращаться уже некуда (рис 45.3).

Way является текущим путем, но в процессе работы необходимо хранить и оптимальный путь OptimalWay.

Усовершенствование алгоритма можно произвести следующим образом: не позволять, чтобы длина Way была больше или равна длине OptimalWay. В этом случае, если и будет найден какой-то вариант, он заведомо не будет оптимальным. Такое усовершенствование в общем случае означает, что как только текущий путь станет заведомо неоптимальным, надо вернуться назад. Данное улучшение алгоритма позволяет во многих случаях сильно сократить перебор.

(рис ) Демонстрация алгоритма перебора с возвратом(рис 45.3) /*Описание функции переборного алгоритма методом поиска в глубину */
void Backtracking(int n, int m, int **Maze){
  int Begin, End, Current;
  Begin = (n - 1) * m;
  End = m - 1;
  int *Way, *OptimalWay;
  int LengthWay, LengthOptimalWay;
  Way = new int[n*m];
  OptimalWay = new int[n*m];
  LengthWay = 0;
  LengthOptimalWay = m*n;
  for (int i = 0 ; i < n*m ; i++ )
    Way[i] = OptimalWay[i] = -1;
  int *Dist;
  Dist = new int[n*m];
  for (int i = 0 ; i < n ; i++ )
    for (int j = 0 ; j < m ; j++ )
      Dist[i * m + j] = ( Maze[i][j] == 0 ? 0 : -1 );
  Way[LengthWay++] = Current = Begin;
  while ( LengthWay > 0 ){
    if(Current == End){
      if (LengthWay < LengthOptimalWay){
        for (int i = 0 ; i < LengthWay ; i++ )
          OptimalWay[i] = Way[i];
        LengthOptimalWay = LengthWay;
      }
      if (LengthWay > 0) Way[--LengthWay] = -1;
      Current = Way[LengthWay-1];
    }
    else{
      int Neighbor = -1;
      if ((Current/m - 1) >= 0  !Insert(Way, Current - m) 
        (Dist[Current - m] == 0 || Dist[Current - m] > LengthWay)
         Dist[Current] < LengthOptimalWay)
          Neighbor = Current - m;
      else 
        if ((Current%m - 1) >= 0  !Insert(Way,Current - 1)
          (Dist[Current - 1]== 0 || Dist[Current - 1] > LengthWay)
           Dist[Current] < LengthOptimalWay )
            Neighbor = Current - 1;
        else 
          if ((Current%m + 1) < m  !Insert(Way,Current + 1) 
           (Dist[Current + 1]== 0 || Dist[Current + 1] > LengthWay)
           Dist[Current] < LengthOptimalWay )
            Neighbor = Current + 1;
         else 
           if ((Current/m + 1) < n  !Insert(Way,Current + m) 
            (Dist[Current + m]== 0 || Dist[Current + m] > LengthWay)
            Dist[Current] < LengthOptimalWay )
             Neighbor = Current + m;
      if ( Neighbor != -1 ){
        Way[LengthWay++] = Neighbor;
        Dist[Neighbor] = Dist[Current] + 1;
        Current = Neighbor;
      }
      else {
        if (LengthWay > 0) Way[--LengthWay] = -1;
        Current = Way[LengthWay-1];
      }
    }
  }
  if ( LengthOptimalWay < n*m ) 
    cout << endl << "Yes. Length way=" << LengthOptimalWay<< endl;
  else cout << endl << "No" << endl;
}

Волновой алгоритм

Этот переборный алгоритм, который основан на поиске в ширину, состоит из двух этапов:

Распространение волны и есть собственно поиск в ширину, при котором клетки помечаются номером шага метода, на котором клетка посещается. При обратном ходе, начиная с конечной вершины, идет восстановление пути, по которому в нее попали путем включения в него клеток с минимальной пометкой (рис 45.4). Важной особенностью является то, что восстановление начинается с конца (с начала оно зачастую невозможно).

Заметим, что перебор методом поиска в ширину по сравнению с перебором с возвратом, как правило, требует больше вспомогательной памяти, которая необходима для хранения информации, чтобы построить путь при обратном ходе и пометить посещенные вершины. Однако он работает быстрее, так как совершенно исключается посещение одной и той же клетки более чем один раз.

Ключевые термины

Алгоритм Дейкстры – это алгоритм нахождения кратчайшего пути от одной из вершин графа до всех остальных, который работает только для графов без ребер отрицательного веса.

Алгоритм Флойда – это алгоритм поиска кратчайшего пути между любыми двумя вершинами графа.

Волновой алгоритм – это переборный алгоритм, который основан на поиске в ширину и состоит из двух этапов: распространение волны и обратный ход.

Кратчайший путь – это путь в графе, то есть последовательность вершин и ребер, инцидентных двум соседним вершинам, и его длина.

Переборный алгоритм – это алгоритм обхода графа, основанный на последовательном переборе возможных путей.

Краткие итоги

Лабораторная работа 45. Алгоритмы на графах. Алгоритмы нахождения кратчайшего пути

Цель работы: изучить основные алгоритмы поиска кратчайшего пути и научиться решать задачи поиска кратчайшего пути на основе алгоритмов Дейкстры, Флойда и переборных алгоритмов.

При выполнении лабораторной работы для каждого задания требуется написать программу на языке С++, которая получает на входе числовые данные, выполняет их обработку в соответствии с требованиями задания и выводит результат на экран. Для обработки данных необходимо реализовать алгоритмы поиска кратчайшего пути на графе на основе алгоритмов Дейкстры, Флойда и переборных алгоритмов в соответствии с постановкой задачи. Ввод данных осуществляется из файла с учетом требований к входным данным, содержащихся в постановке задачи. Ограничениями на входные данные является допустимый диапазон значений используемых числовых типов в языке С++.

Теоретические сведения.

Ознакомьтесь с материалом лекции 45.

Задания к лабораторной работе.

Выполните приведенные ниже задания.

На основании приведенной в лекции 45 функций реализуйте программы, в которых выполняются алгоритм Дейкстры и алгоритм Флойда.

На основании приведенной в лекции функции реализуйте программу, в которой выполняется переборный алгоритм методом поиска в ширину.

Оля (A), Маша (B), Витя (C), Дима (D), Ваня (E) и Катя (F) живут в разных городах. Стоимость билетов из разных городов известна (рис.). Добраться до городов можно разными способами. Определить наименьшую сумму, которую нужно потратить, чтобы Оля могла навестить каждого из своих друзей.

Квадратное озеро задается матрицей MxN и покрыто мелкими островками. В левом верхнем углу находится плот размером mxm. За один шаг плот может передвигаться на одну клетку по вертикали или горизонтали. Требуется определить кратчайший путь плота до правого нижнего угла.

Напишите алгоритм, находящий строку длиной 100 символов, состоящую только из букв "A", "B", "C", такую, что в ней никакие две соседние подстроки не равны друг другу. Воспользуйтесь перебором с возвратом.

Указания к выполнению работы.

Каждое задание необходимо решить в соответствии с изученными алгоритмами поиска кратчайшего пути на графе на основе алгоритмов Дейкстры, Флойда и переборных алгоритмов, реализовав программный код на языке С++. Рекомендуется воспользоваться материалами лекции 45, где подробно рассматриваются описания алгоритмов поиска кратчайшего пути на графе, примеры разработки функций, реализующих алгоритмы поиска на графе, на языке С++. Программу для решения каждого задания необходимо разработать методом процедурной абстракции, используя функции. Этапы решения сопроводить комментариями в коде. В отчете следует отразить разработку и обоснование математической модели решения задачи, представить результаты тестирования программ.

Следует реализовать каждое задание в соответствии с приведенными этапами:

Требования к отчету.

Отчет по лабораторной работе должен соответствовать следующей структуре.

Контрольные вопросы