If I have a weighted oriented graph, with costs being in the set {x, y} ( so they can only take two values), how can I find the minimum distance from a source vertex to all the vertices in O(V + E) ?
1 Answers
There's this post that talks about 0-1 BFS, and I found that the writer asked whether we can make the same algorithm (0-1 BFS) solve the problem when weights are x and y (not 0 and 1), and I found this comment which mentions an algorithm that I couldn't prove to be wrong (but did not test it yet).
Here's the comment: https://codeforces.com/blog/entry/22276?#comment-268883
I'd like to know if you can find some way to prove/disprove this algorithm.
Related