Раздел «Образование».FIVTLecturesTerm4Lecture01:
<< Список лекций ФИВТ, 4-й семестр, 2009 г.

Лекция 1. Графы. Обход в ширину. Алгоритм Дейкстры

Задача Лабиринт

Понятие графа. Вершины. Ребра. Смежные вершины. Ориентированный граф. Задача Лабиринт (PROBLEM:112). Идея волны. Использование очереди для хранения текущего "фронта волны".

// q - некоторый контейнер, например, очередь и insert == enqueue,  extract == dequeue
// S - вершина графа, из которой мы ищем кратчайшие пути в остальные вершины
S.depth = 0;
S.color = GREY;
q.insert(S);
while ( !q.is_empty() ) {
  v = q.extract();
  foreach w in (Adj(v)) {
     if (w.color == WHITE) {
       w.depth = v.depth + 1;
       w.color = GREY;
       q.insert(w)
     }
  }
  v.color = BLACK;
}

Время работы = O(E), E - количество рёбер.

Если q - очередь, то данный псевдокод описывает алгоритм обхода графа в ширину.

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

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

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

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

Определение: U = Множество вершин, которые мы извлели из очереди. V/U - остальные вершины.

Алгоритм: на каждом шаге мы переносим вершину с минимальным ключем (обозначим ее v) из V/U в U. Для каждой её смежной вершины w мы выполняем обновление ключа по формуле :w.key = min ( w.key, v.key + weight(w,v) ), где weight(w,v) - верс ребра (w,v).

// q - очередь с приоритетом. Метод extract == extract_min_by_key
// S - вершина графа, из которой мы ищем кратчайшие пути
S.key = 0;  // ключ S устанавливаем в 0
foreach v in V / S { v.key = +infty; } // ключи остальных — в +бесконечность
foreach v in V { q.insert( v ); } // помещаем все вершины в q
while ( !q.is_empty() ) {
  v = q.extract(); // извлекаем вершину с минимальным ключом
  foreach w in (Adj(v)) {
     if (w.color == WHITE) {
        // обновляем ключ вершины v
        // устанавливаем его в v.key + weight(w,v), 
        // если это число меньше текущего ключа w, то есть
        // w.key = min ( w.key, v.key + weight(w,v) )
        q.update_key(w, v.key + weight(w,v) );
     }
  }
  v.color = BLACK;
}

Утверждение 1. В каждый момент времени ключ некоторой вершины v равен длине кратчайшего пути, который только возможен, если двигаться исключительно по вершинам из U. Только сама, последняя вершина v может не принадлежать U.

Утверждение 2. Если v принадлежит U, то ключ равен кратчайшему пути из S в v.

Эти два утверждения доказываются методом математической индукции.