Графы для самых маленьких: BFS 0-1

в 14:08, , рубрики: bfs, Алгоритмы, графы, метки: , ,

Добрый день, уважаемыее!
В предыдущих постах уже рассказывалось о двух алгоритмах, с помощью которых можно найти путь сквозь лабиринт: DFS и BFS. Всех, кто хочет еще немного поиздеваться над нашим лабиринтом, прошу под кат.

Новая постановка задачи

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

Решение

Мы уже знаем один алгоритм, позволяющий найти кратчайший путь — это BFS, соответственно, хочется придумать какой-то алгоритм на его основе.
Графы для самых маленьких: BFS 0 1Если мы применим BFS в его обычном виде к графу, изображенному на рисунке, произойдет ошибка: расстояние до вершины 2 будет посчитано при обработке вершины 1, после чего может начаться обработка вершины 2, несмотря на то, что расстояние до нее не является оптимальным. Ошибка произошла из-за того, что был нарушен основной инвариант BFS: вершины рассматривались не в порядке увеличения расстояния.
Для того, чтобы вершины рассматривались в порядке увеличения расстояния, нужно добавлять вершины, к которым ведут ребра веса 0, в начало очереди (и, таким образом, использовать не очередь, а дек).

Реализация

Предполагается, что граф представлен в виде vector<vector<pair<int,int>>> edges, где edges[v] — массив ребер, исходящих из вершины v. Каждое ребро задается парой чисел — номером конечной вершины и весом.
Расстояния до вершин хранятся в vector<int> d, причем изначально все элементы этого массива — числа, заведомо большие, чем расстояния до всех вершин.

BFS 0-1

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

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js