0-1 BFS
· 5 min · bfs
Problem :
Given an undirected graph with binrary edge weights, find the shortest distance path between a source and destination node.Solution :
Yes, Dijkstra, but is there a better soltuion? => 0 - 1 BFS even in the worst case, dijkstra can go upto O(E + VlogV) using fibonacci heaps, 0 - 1 BFS using a deque can do it in linear time 🤯 O(E + V).Tip :
not only for binary weights, but can use for any weights of form {0, x} -> (x >= 0)
more coming soon : …