Hello. The bfs article says that

Finding the shortest path in a 0-1-graph (i.e., a weighted graph, but with weights equal to only 0 or 1): modifying the search in width is enough: if the current edge is of zero weight, and the distance to some vertex is improved, then we add this vertex not to the end, but to the beginning of the queue.

How to check the improvement distance to some vertex for rational asymptotics, and how to continue to work with it, because that peak, the distance to which improved could be “set on fire” almost at the very beginning, and then you have to go all over again.

UPDATE

Tried to go the way of another article . The question arises: if there are edges from vertex 1-2 (weight 1) and 1-3 (weight 0) and 3-2 (weight 0) and 2-1 (weight 0), then the algorithm from vertex 1 will put dist 2 = 1; dist [3] = 0; but from 3 to 2 can not go, because it is used. What to do?

  • one
    Now I’ve opened the IDE, I copied the code from the article and I realized that I’m too lazy to understand it ... Show the code that you tried to write yourself (or correct) and say that it’s bad. Because need to carefully change the two lines. - Alexey Lobanov
  • Update: "1-2 (weight 1)" and "2-1 (weight 0)" - parallel edges with different weight? Or is it an undirected graph and parallel edges? - Alexey Lobanov
  • The graph is oriented, the edges are parallel, but directed in different directions and have different weights - stepbystep

1 answer 1

In this modification of the algorithm, it is not necessary to use the used array. For each edge, you need to check if there is a better way than the one that has already been found for the finite vertex of the edge. And if the new path is better, add a vertex to the beginning / end of the queue depending on the cost of the edge. It is easy to show that at any moment in time only vertices can be in the queue, the distance to which is equal to x and, possibly, x + 1. Moreover, all vertices with distance x go before all vertices with distance x + 1. From this it follows that any vertex will get into the queue no more than two times. Proof: if at the first hit in the queue, there are no vertices with a smaller distance left in the queue, then the added vertex will not enter the queue again, since there are no vertices that can relax the distance to it. If there are still peaks in the queue with a distance of less than 1, then they will be able to improve the distance to the one added only once, and then it will fall into the queue a second time. Thus, the asymptotic behavior of O (N + M) is preserved.