Counts for the smallest: BFS 0-1
Good afternoon, dear habrovchane!
In previous posts, we already talked about two algorithms with which you can find a way through the maze: DFS and BFS . Anyone who wants a little more to mock our labyrinth, please under the cat.
Add teleports to the labyrinth - now in some rooms there will be devices using which you can get into another room in zero time.
Or, to put it more formally, now each edge is labeled with the time it takes to go through it — it is 0 or 1. And the goal is still the same - to find the shortest in terms of time path from the initial vertex to the final one.
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 main BFS invariant was violated: the vertices were not considered in the order of increasing distance.
In order for vertices to be considered in order of increasing distance, you need to add vertices to which the edges of weight 0 lead to the beginning of the queue (and, thus, use not a queue, but decks).
The distances to the vertices are stored in vector <int> d, and initially all the elements of this array are numbers that are obviously larger than the distances to all the vertices.
Each vertex, obviously, gets into decks no more than two times, so the amount of memory used by the algorithm is O (V).
In previous posts, we already talked about two algorithms with which you can find a way through the maze: DFS and BFS . Anyone who wants a little more to mock our labyrinth, please under the cat.
New problem statement
Add teleports to the labyrinth - now in some rooms there will be devices using which you can get into another room in zero time.
Or, to put it more formally, now each edge is labeled with the time it takes to go through it — it is 0 or 1. And the goal is still the same - to find the shortest in terms of time path from the initial vertex to the final one.
Decision
We already know one algorithm that allows us 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 main BFS invariant was violated: the vertices were not considered in the order of increasing distance.
In order for vertices to be considered in order of increasing distance, you need to add vertices to which the edges of weight 0 lead to the beginning of the queue (and, thus, use not a queue, but decks).
Implementation
It is assumed that the graph is represented as vector <vector <pair <int, int >>> edges, where edges [v] is an array of edges emanating from the vertex v. Each edge is defined by a pair of numbers — the number of the final vertex and the weight.The distances to the vertices are stored in vector <int> d, and initially all the elements of this array are numbers that are obviously larger than the distances to all the vertices.
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); } } } } } Algorithm complexity
For each edge and each vertex, a constant number of actions is performed, therefore the time complexity of the algorithm is O (V + E).Each vertex, obviously, gets into decks no more than two times, so the amount of memory used by the algorithm is O (V).
')
Source: https://habr.com/ru/post/200560/
All Articles