Добрый день, уважаемыее!
В предыдущих постах уже рассказывалось о двух алгоритмах, с помощью которых можно найти путь сквозь лабиринт: DFS и BFS. Всех, кто хочет еще немного поиздеваться над нашим лабиринтом, прошу под кат.
Новая постановка задачи
Добавим в лабиринт телепорты — теперь в некоторых комнатах будут находиться устройства, используя которые можно попасть в другую комнату за нулевое время.
Или, говоря более формально, теперь каждое ребро помечено временем, которое требуется на переход по нему — это 0 или 1. А цель все та же — найти кратчайший с точки зрения времени путь из начальной вершины в конечную.
Решение
Мы уже знаем один алгоритм, позволяющий найти кратчайший путь — это BFS, соответственно, хочется придумать какой-то алгоритм на его основе.
Если мы применим BFS в его обычном виде к графу, изображенному на рисунке, произойдет ошибка: расстояние до вершины 2 будет посчитано при обработке вершины 1, после чего может начаться обработка вершины 2, несмотря на то, что расстояние до нее не является оптимальным. Ошибка произошла из-за того, что был нарушен основной инвариант BFS: вершины рассматривались не в порядке увеличения расстояния.
Для того, чтобы вершины рассматривались в порядке увеличения расстояния, нужно добавлять вершины, к которым ведут ребра веса 0, в начало очереди (и, таким образом, использовать не очередь, а дек).
Реализация
Предполагается, что граф представлен в виде vector<vector<pair<int,int>>> edges, где edges[v] — массив ребер, исходящих из вершины v. Каждое ребро задается парой чисел — номером конечной вершины и весом.
Расстояния до вершин хранятся в vector<int> d, причем изначально все элементы этого массива — числа, заведомо большие, чем расстояния до всех вершин.
void BFS()
{
// Инициализация
deque<int> q;
q.push_back(start);
d[start] = 0;
// Главный цикл
while (!q.empty())
{
// Достаем вершину
int v = q.front();
q.pop_front();
// Смотрим на всех ее соседей
for (int i = 0; i < (int)edges[v].size(); ++i)
{
// Если можно улучшить известное расстояние
if (d[edges[v][i].first] > d[v] + edges[v][i].second)
{
// То улучшаем его и добавляем вершину в дек
d[edges[v][i].first] = d[v] + edges[v][i].second;
// Если ребро бесплатное, то в начало
if (edges[v][i].second == 0)
{
q.push_front(edges[v][i].first);
}
// Иначе - в конец
else
{
q.push_back(edges[v][i].first);
}
}
}
}
}
Сложность алгоритма
Для каждого ребра и каждой вершины выполняется константное количество действий, поэтому временная сложность алгоритма — O(V+E).
Каждая вершина, очевидно, попадает в дек не более двух раз, поэтому количество используемой алгоритмом памяти — O(V).
Автор: alexeykuzmin0
