logoNEURAL COOK
SearchAll PostsTagsNotesAuthor
logoNEURAL COOK

A posts created with Next.js and Tailwind.css

Explore

  • All posts
  • Notes
  • Snippets
  • Tags
  • RSS feed

Connect

instagramlinkedinmailgithub

© 2026 VIKI. All rights reserved.

Built with
Contents
ArraysBoyer-Moore Majority Vote AlgorithmKadane’s AlgorithmTriple Reverse algorithm aka Reversal Algorithm
DP Patterns
Cycle detectionDisjoint Set UnionGraphTopological SortTraversal algorithmsTree Traversal
0-1-BFSBellman-Ford AlgorithmDijkstra
Binary HeapBinomial HeapHeap
Cycle DetectionLinked ListSorting
Finding the majority elementRotate array by K steps
Finding If Number is PrimeGCD of two numbersPerforming ExponentiationPrime NumbersRandomising Data
3. Max Consecutive OnesHoare'S Partition SchemeLomuto Partition Scheme
DequesPriority QueueQueue
The Binary Search Master GuideThe Rotated Sorted Array Master Guide
Bubble SortCounting SortInsertion SortMerge SortPigeon Hole SortQuick SortSelection Sort
Monotonic StackMonotonic StackStackReversing an ArrayStackTower of Hanoi
Binary Tree TraversalCentre of gravityDiameter of TreeShortest Path
Algorithmic Pattern/graph/shortest path algorithm

0-1-BFS

2 min read
On this pageImplementation
Implementation

0-1 BFS is a shortest-path algorithm used when every edge has a weight of either 0 or 1. It is an optimized version of BFS that uses a Deque (Double-Ended Queue) instead of a normal queue.

The main idea:

  • If an edge has weight 0, add the next vertex to the front of the deque.
  • If an edge has weight 1, add the next vertex to the back of the deque.

This ensures that vertices with smaller tentative distances are processed first.

Normal BFS works when all edges have equal weight (typically weight 1). Dijkstra works with arbitrary nonnegative edge weights, but it uses a priority queue.

But what if all edges have only weights 0 and 1? We can use 0-1 BFS, which is simpler and often faster than Dijkstra

# Implementation

import java.util.*;
 
class Solution {
 
    public int[] zeroOneBFS(
            int n,
            List<List<int[]>> graph,
            int source) {
 
        final int INF = Integer.MAX_VALUE;
 
        int[] dist = new int[n];
        Arrays.fill(dist, INF);
 
        Deque<int[]> deque = new ArrayDeque<>();
 
        dist[source] = 0;
        deque.addFirst(new int[]{source, 0});
 
        while (!deque.isEmpty()) {
 
            int[] current = deque.pollFirst();
 
            int u = current[0];
            int currentDist = current[1];
 
            // Ignore outdated deque entries
            if (currentDist != dist[u]) {
                continue;
            }
 
            for (int[] edge : graph.get(u)) {
 
                int v = edge[0];
                int weight = edge[1];
 
                int newDist = dist[u] + weight;
 
                if (newDist < dist[v]) {
 
                    dist[v] = newDist;
 
                    if (weight == 0) {
                        deque.addFirst(new int[]{v, newDist});
                    } else {
                        deque.addLast(new int[]{v, newDist});
                    }
                }
            }
        }
 
        return dist;
    }
}
←PreviousStrongly Connected ComponentNext→Bellman-Ford Algorithm

On this page

Implementation