Counts for the smallest: BFS 0-1

    Good afternoon, dear Khabrovites!
    In previous posts, we already talked about two algorithms with which you can find the way through the maze: DFS and BFS . Anyone who wants to make fun of our labyrinth a little more, please, under cat.

    New statement of the problem


    Add teleports to the maze - now in some rooms there will be devices using which you can get into another room in zero time.
    Or, speaking more formally, now each edge is marked with the time it takes to go along it - it’s 0 or 1. But the goal is the same - to find the shortest path from the point of view of time from the initial vertex to the final one.

    Decision

    We already know one algorithm that allows you to find the shortest path - this is BFS, respectively, I want to come up with some kind of algorithm based on it.
    If we apply BFS in its usual form to the graph shown in the figure, an error will occur: the distance to vertex 2 will be calculated when processing vertex 1, after which processing of vertex 2 may begin, despite the fact that the distance to it is not optimal. The error occurred because the basic BFS invariant was violated: the vertices were not considered in the order of increasing distance.
    In order for the vertices to be considered in the order of increasing distance, you need to add the vertices to which the edges of weight 0 lead to the beginning of the queue (and thus use not the queue, but the deck).

    Implementation

    It is assumed that the graph is represented as vector>> edges, where edges [v] is an array of edges emanating from vertex v. Each edge is defined by a pair of numbers - the number of the final vertex and weight.
    The distances to the peaks are stored in vector d, and initially all the elements of this array are numbers that are known to be larger than the distances to all the vertices.
    BFS 0-1
    void BFS()
    {
        // Инициализация
        deque 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);
                    }
                }
            }
        }
    }
    


    Algorithm complexity

    A constant number of actions is performed for each edge and each vertex; therefore, the time complexity of the algorithm is O (V + E).
    Each vertex, obviously, gets to the deck no more than two times, so the amount of memory used by the algorithm is O (V).

    Also popular now: