Why it works

Deque maintains monotonic distance order. 0-weight neighbor has same distance → front. 1-weight → distance + 1 → back.

Advertisement

Implementation

int[] zeroOneBfs(int src, List[] graph) {
  int[] dist = new int[graph.length];
  Arrays.fill(dist, Integer.MAX_VALUE);
  dist[src] = 0;
  Deque dq = new ArrayDeque<>();
  dq.offerFirst(src);
  while (!dq.isEmpty()) {
    int u = dq.pollFirst();
    for (int[] edge : graph[u]) {
      int v = edge[0], w = edge[1];
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        if (w == 0) dq.offerFirst(v);
        else dq.offerLast(v);
      }
    }
  }
  return dist;
}
Advertisement

Applications

Grid problems with free direction / wall crossing = 1 cost. Torch light problems. Word ladder with hints.

vs Dijkstra

Same effect, O(V+E) instead of O((V+E) log V). Big win when 0/1 weights.