title: How to find shortest path in a directed graph that has edge weights either 0 or 1 in linear time?
body: <p>I am looking for a way to augment the BFS method used to find the single source shortest paths in an unweighted directed graph and solve the above problem in O(N+M) time. 
  where N is the number of vertices, M is the number of edges</p>
  
  <p>I have thought the following:</p>
  
  <ol>
  <li><p>Contract the vertices of the graph that have an edge weight 0 between them. But this would definitely be wrong as then I would be changing the graph's properties and adding new edges to vertices that originally had none.</p></li>
  <li><p>Changing the edge weights to 1 and 2. And then creating dummy vertices in the paths that are of length 2 to convert those edges to edges of weight 1. But this would give the wrong answer.</p></li>
  </ol>
  
  <p>In more generality, how can I find single source shortest paths in a directed graph when the edge weights are between 0 and MAX in linear time. (MAX is the maximum edge weight)</p>