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

Добрый день, уважаемые хабровчане!

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

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

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

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

Решение

Мы уже знаем один алгоритм, позволяющий найти кратчайший путь — это BFS, соответственно, хочется придумать какой-то алгоритм на его основе.

Если мы применим BFS в его обычном виде к графу, изображенному на рисунке, произойдет ошибка: расстояние до вершины 2 будет посчитано при обработке вершины 1, после чего может начаться обработка вершины 2, несмотря на то, что расстояние до нее не является оптимальным. Ошибка произошла из-за того, что был нарушен основной инвариант BFS: вершины рассматривались не в порядке увеличения расстояния.

Для того, чтобы вершины рассматривались в порядке увеличения расстояния, нужно добавлять вершины, к которым ведут ребра веса 0, в начало очереди (и, таким образом, использовать не очередь, а дек).

Реализация

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

Расстояния до вершин хранятся в vector 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).

This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at fivefilters.org/content-only/faq.php#publishers. Five Filters recommends:

• Massacres That Matter - Part 1 - 'Responsibility To Protect' In Egypt, Libya And Syria


• Massacres That Matter - Part 2 - The Media Response On Egypt, Libya And Syria


• National demonstration: No attack on Syria - Saturday 31 August, 12 noon, Temple Place, London, UK