DSA-116 · Dijkstra’s two distance levels implemented with a deque

0–1 BFS — Binary Edge Weights

Advanced · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 121458 deterministic checks. Learner drafts are not executed.

Understand the problem

Given a directed graph whose edge weights are exactly zero or one, return the minimum cost from source to every declared vertex. Return −1 for unreachable vertices in a fresh long array.

n is a positive vertex count; vertices are 0..n−1, including isolated vertices. source must be in that range. edges is a nonnull int[][] of nonnull triples [from,to,weight]. Edges are directed; self-loops, repeated rows, parallel edges, and zero weights are valid. Null outer input throws NullPointerException; malformed triples, invalid labels, or forbidden weights throw IllegalArgumentException before traversal. Every weight must be 0 or 1; any other int weight throws IllegalArgumentException. Size preconditions: n≤100,000 and at most 200,000 edge occurrences.
binaryDistances(n,edges,source) returns a fresh long[n]. Entry source is zero. Distances measure total edge weight, not number of hops: arbitrarily many zero edges can cost zero. Source is a valid zero-based label and all n output positions exist, including isolated labels.
Preserve source values and row identities, including shared row objects. No sorting or marking may alter the caller’s arrays. Auxiliary graph entries are privately allocated. Input must not be modified concurrently. The returned array is independent on every call. Long.MAX_VALUE is a private infinity sentinel and is converted to −1 only after traversal.

Examples

Input: n=4, edges=[[0,1,1],[0,2,0],[2,1,0]], source=0
Output: [0,0,0,−1]
The zero-cost two-hop route improves vertex one after its initial cost-one discovery.
Input: n=3, edges=[[0,1,0],[1,0,0],[1,2,1]], source=0
Output: [0,0,1]
Strict relaxation stops the zero cycle from generating repeated equal entries.

Before you start

Shortest-path relaxation and why first discovery need not be final
Deque front/back operations and zero-cost transitions

Recognize the structure

Ordinary BFS orders by hop count and works only when all useful edges have the same positive cost. Binary weights offer an intermediate structure: from current cost d, a relaxation proposes only d or d+1. Put same-cost work at the front and next-cost work at the back. This supplies the minimum-label ordering needed by Dijkstra without a logarithmic heap operation.

Try before revealing

Hint 1

What two costs can a processed distance d propose?

Hint 2

Zero-cost work belongs before pending d+1 work.

Hint 3

Push strict zero improvements to the front, one improvements to the back, and skip stale stored costs.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Lazy-heap Dijkstra

Use the same strict relaxation and immutable [cost,vertex] snapshots with a PriorityQueue ordered by cost then vertex ID. Skip stale costs when removed. It is correct for all nonnegative weights, but this API validates binary weights in both methods so they share exactly one contract. The baseline gives an alternate frontier implementation against which the deque can be checked.

Improve the baseline

Initialize a private adjacency list and labels

Set all labels infinite, source zero, and enqueue (0,source) at the front. Each adjacency entry owns its destination/weight pair. Input order determines the neighbor scan order; parallel occurrences remain distinct, and source arrays are never used as marks.

Use zero-front and one-back insertion

Pop the front snapshot. If its cost differs from the current label, discard it. Otherwise compute candidate=cost+weight. Only a strict improvement changes distance[next]; a zero edge pushes its new snapshot to the front, and a one edge pushes it to the back. A zero insertion can become the very next pop.

Expose unreachable values after work is done

When the deque is empty, every reachable label is final. Translate only the remaining infinity positions to −1 and return the fresh label array. Do not translate during traversal, because −1 would look cheaper than every legitimate candidate and interfere with comparison.

Why it is correct

Two-level frontier ordering

Initially the deque contains only cost zero. When a front snapshot has cost d, all remaining snapshots have cost d or d+1 in nondecreasing order. New zero-edge proposals have cost d and go before them; new one-edge proposals have cost d+1 and go after them. A stale pop adds nothing, so it preserves this ordering. The two-level property concerns stored costs, not mutable vertex labels.

Valid front pops finalize distances

Because the deque yields the minimum snapshot cost, a nonstale pop has the same finality argument as nonnegative Dijkstra. A hypothetical cheaper route would expose an earlier crossing-edge proposal before this pop. A stale proposal has been superseded and must not scan edges again.

Strict relaxation terminates zero cycles

Every label is a witnessed route cost. Equal candidates add nothing, so following a zero-cost cycle back to an already equal label cannot enqueue endlessly. Each vertex has only one nonstale pop; its outgoing occurrences are scanned once, and only those scans can create additional snapshots. Exhaustion gives shortest costs for every reachable vertex.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.*;
public final class Solution {
    private static void validate(int n,int[][] edges,int source) {
        Objects.requireNonNull(edges,"edges");
        if(n<1||source<0||source>=n)throw new IllegalArgumentException("invalid universe or source");
        for(int[] e:edges)if(e==null||e.length!=3||e[0]<0||e[0]>=n||e[1]<0||e[1]>=n||e[2]<0||e[2]>1)throw new IllegalArgumentException("invalid weighted edge");
    }
    private record Entry(long cost,int vertex) {}
    private static final Comparator<Entry> ORDER=Comparator.comparingLong(Entry::cost).thenComparingInt(Entry::vertex);
    private static List<List<int[]>> graph(int n,int[][] edges) {
        List<List<int[]>> graph=new ArrayList<>();for(int v=0;v<n;v++)graph.add(new ArrayList<>());
        for(int[] e:edges)graph.get(e[0]).add(new int[]{e[1],e[2]});return graph;
    }
    public static long[] binaryDistances(int n,int[][] edges,int source) {
        validate(n,edges,source);var graph=graph(n,edges);long[] distance=new long[n];Arrays.fill(distance,Long.MAX_VALUE);distance[source]=0;
        ArrayDeque<Entry> deque=new ArrayDeque<>();deque.addFirst(new Entry(0,source));
        while(!deque.isEmpty()) {
            Entry current=deque.removeFirst();int v=current.vertex();
            if(current.cost()!=distance[v])continue;
            for(int[] edge:graph.get(v)) {
                int next=edge[0];long candidate=current.cost()+edge[1];
                if(candidate<distance[next]) {
                    distance[next]=candidate;Entry entry=new Entry(candidate,next);
                    if(edge[1]==0)deque.addFirst(entry);else deque.addLast(entry);
                }
            }
        }
        for(int v=0;v<n;v++)if(distance[v]==Long.MAX_VALUE)distance[v]=-1;return distance;
    }
    public static long[] baseline(int n,int[][] edges,int source) {
        validate(n,edges,source);var graph=graph(n,edges);long[] d=new long[n];Arrays.fill(d,Long.MAX_VALUE);d[source]=0;PriorityQueue<Entry> q=new PriorityQueue<>(ORDER);q.add(new Entry(0,source));
        while(!q.isEmpty()){Entry e=q.remove();if(e.cost()!=d[e.vertex()])continue;for(int[] edge:graph.get(e.vertex())){long candidate=e.cost()+edge[1];if(candidate<d[edge[0]]){d[edge[0]]=candidate;q.add(new Entry(candidate,edge[0]));}}}
        for(int v=0;v<n;v++)if(d[v]==Long.MAX_VALUE)d[v]=-1;return d;
    }
}

Read the meaningful blocks

Store a cost snapshot, not just a moving key

Entry(cost,vertex) lets the loop distinguish old proposals from current ones. The walkthrough’s frontier is the exact front-to-back snapshot sequence, unlike a heap’s sorted logical picture. A stale cost-one entry can remain after the same vertex finalized at zero.

Front/back is tied to weight, not destination

Enqueue a strict zero improvement with addFirst and a strict one improvement with addLast. Using addLast for everything produces FIFO order by discovery rather than cost, invalidating the one-final-pop argument and the linear bound.

No visited-on-enqueue shortcut

A first discovery at one can later improve to zero. Marking it final when enqueued rejects the better route. Here the current snapshot check supplies the correct processing rule; no caller-owned marker and no recursive stack are needed.

Complexity

For V vertices and E edge occurrences, validation plus adjacency construction is O(V+E). Every vertex has at most one nonstale pop, so every outgoing occurrence is scanned once. At most E strict improvements create additional snapshots, each inserted and removed in O(1) amortized deque time. Total main time is O(V+E), with O(V+E) auxiliary storage for adjacency and possible duplicate snapshots. The returned fresh array contains V longs; separating output still leaves adjacency/frontier storage.

The heap baseline takes O(V+E+(E+1)log(E+2)) time and O(V+E) auxiliary storage for arbitrary parallel occurrences. Both preserve the source. The trace’s settled history and per-operation copies are teaching records, not extra state needed by Java.

Exact-state walkthroughs

Reveal normal and boundary traces

Zero detour supersedes a one-cost proposal

Input: {"n":4,"edges":[[0,1,1],[0,2,0],[2,1,0],[1,2,0]],"source":0} · Fresh binary shortest distances: [0,0,0,-1]

Step 1 of 11: Seed a cost-zero snapshot for the source.

Distances are tentative; null is infinity, represented by Long.MAX_VALUE in Java. Frontier pairs are [cost snapshot, vertex]. Heap pairs are shown in sorted removal order; deque pairs are exact front-to-back order.

Binary weights — exact deque order and cost snapshots

Phase: initial.

Source: 0. Every label 0..3 exists; edge direction matters.

Directed edge occurrences — from → to : weight

0: 0 → 1 : 1
1: 0 → 2 : 0
2: 2 → 1 : 0
3: 1 → 2 : 0

Vertex arrival costs — tentative and final are separate

vertex 0cost: 0tentative
vertex 1cost: ∞ (no finite label)not reached
vertex 2cost: ∞ (no finite label)not reached
vertex 3cost: ∞ (no finite label)not reached

Deque — exact front → back snapshot order

0: [cost 0, vertex 0]

Only binary weights support this two-level deque ordering. Strict improvements stop equal-cost cycles from re-enqueueing forever.

∞ is displayed as null in the exact state table and means Java Long.MAX_VALUE. Final unreachable results use −1. Input values and row identities stay unchanged. Histories and logical frontier pictures are teaching views, excluded from Java workspace.

State after this step
Variable	Value
input	`{"n":4,"edges":[[0,1,1],[0,2,0],[2,1,0],[1,2,0]],"source":0}`
rows	`0`
cols	`0`
distance	`[0,null,null,null]`
frontier	`[[0,0]]`
settled	`[]`
phase	`"initial"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static void validate(int n,int[][] edges,int source) {
 4         Objects.requireNonNull(edges,"edges");
 5         if(n<1||source<0||source>=n)throw new IllegalArgumentException("invalid universe or source");
 6         for(int[] e:edges)if(e==null||e.length!=3||e[0]<0||e[0]>=n||e[1]<0||e[1]>=n||e[2]<0||e[2]>1)throw new IllegalArgumentException("invalid weighted edge");
 7     }
 8     private record Entry(long cost,int vertex) {}
 9     private static final Comparator<Entry> ORDER=Comparator.comparingLong(Entry::cost).thenComparingInt(Entry::vertex);
10     private static List<List<int[]>> graph(int n,int[][] edges) {
11         List<List<int[]>> graph=new ArrayList<>();for(int v=0;v<n;v++)graph.add(new ArrayList<>());
12         for(int[] e:edges)graph.get(e[0]).add(new int[]{e[1],e[2]});return graph;
13     }
14     public static long[] binaryDistances(int n,int[][] edges,int source) {
15         validate(n,edges,source);var graph=graph(n,edges);long[] distance=new long[n];Arrays.fill(distance,Long.MAX_VALUE);distance[source]=0;
16         ArrayDeque<Entry> deque=new ArrayDeque<>();deque.addFirst(new Entry(0,source));
17         while(!deque.isEmpty()) {
18             Entry current=deque.removeFirst();int v=current.vertex();
19             if(current.cost()!=distance[v])continue;
20             for(int[] edge:graph.get(v)) {
21                 int next=edge[0];long candidate=current.cost()+edge[1];
22                 if(candidate<distance[next]) {
23                     distance[next]=candidate;Entry entry=new Entry(candidate,next);
24                     if(edge[1]==0)deque.addFirst(entry);else deque.addLast(entry);
25                 }
26             }
27         }
28         for(int v=0;v<n;v++)if(distance[v]==Long.MAX_VALUE)distance[v]=-1;return distance;
29     }
30     public static long[] baseline(int n,int[][] edges,int source) {
31         validate(n,edges,source);var graph=graph(n,edges);long[] d=new long[n];Arrays.fill(d,Long.MAX_VALUE);d[source]=0;PriorityQueue<Entry> q=new PriorityQueue<>(ORDER);q.add(new Entry(0,source));
32         while(!q.isEmpty()){Entry e=q.remove();if(e.cost()!=d[e.vertex()])continue;for(int[] edge:graph.get(e.vertex())){long candidate=e.cost()+edge[1];if(candidate<d[edge[0]]){d[edge[0]]=candidate;q.add(new Entry(candidate,edge[0]));}}}
33         for(int v=0;v<n;v++)if(d[v]==Long.MAX_VALUE)d[v]=-1;return d;
34     }
35 }
36

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Seed a cost-zero snapshot for the source.
Distances are tentative; null is infinity, represented by Long.MAX_VALUE in Java. Frontier pairs are [cost snapshot, vertex]. Heap pairs are shown in sorted removal order; deque pairs are exact front-to-back order.
input
{"n":4,"edges":[[0,1,1],[0,2,0],[2,1,0],[1,2,0]],"source":0}
rows
0
cols
0
distance
[0,null,null,null]
frontier
[[0,0]]
settled
[]
phase
"initial"
current
null
Remove the least valid cost and finalize this vertex.
Compare the stored snapshot with the current label before scanning outgoing edges. Equal-cost alternatives do not enqueue, so zero-cost cycles cannot loop indefinitely. A finalized cost cannot later decrease.
input
{"n":4,"edges":[[0,1,1],[0,2,0],[2,1,0],[1,2,0]],"source":0}
rows
0
cols
0
distance
[0,null,null,null]
frontier
[]
settled
[0]
phase
"settle"
current
0
cost
0
Relax and place a strict improvement at the correct deque end.
A failed relaxation leaves both label and frontier unchanged. Weight zero goes to the front; weight one goes to the back. Stale snapshots remain until popped.
input
{"n":4,"edges":[[0,1,1],[0,2,0],[2,1,0],[1,2,0]],"source":0}
rows
0
cols
0
distance
[0,1,null,null]
frontier
[[1,1]]
settled
[0]
phase
"relax"
current
0
cost
0
edgeIndex
0
next
1
weight
1
candidate
1
improved
true
Relax and place a strict improvement at the correct deque end.
A failed relaxation leaves both label and frontier unchanged. Weight zero goes to the front; weight one goes to the back. Stale snapshots remain until popped.
input
{"n":4,"edges":[[0,1,1],[0,2,0],[2,1,0],[1,2,0]],"source":0}
rows
0
cols
0
distance
[0,1,0,null]
frontier
[[0,2],[1,1]]
settled
[0]
phase
"relax"
current
0
cost
0
edgeIndex
1
next
2
weight
0
candidate
0
improved
true
Remove the least valid cost and finalize this vertex.
Compare the stored snapshot with the current label before scanning outgoing edges. Equal-cost alternatives do not enqueue, so zero-cost cycles cannot loop indefinitely. A finalized cost cannot later decrease.
input
{"n":4,"edges":[[0,1,1],[0,2,0],[2,1,0],[1,2,0]],"source":0}
rows
0
cols
0
distance
[0,1,0,null]
frontier
[[1,1]]
settled
[0,2]
phase
"settle"
current
2
cost
0
Relax and place a strict improvement at the correct deque end.
A failed relaxation leaves both label and frontier unchanged. Weight zero goes to the front; weight one goes to the back. Stale snapshots remain until popped.
input
{"n":4,"edges":[[0,1,1],[0,2,0],[2,1,0],[1,2,0]],"source":0}
rows
0
cols
0
distance
[0,0,0,null]
frontier
[[0,1],[1,1]]
settled
[0,2]
phase
"relax"
current
2
cost
0
edgeIndex
0
next
1
weight
0
candidate
0
improved
true
Remove the least valid cost and finalize this vertex.
Compare the stored snapshot with the current label before scanning outgoing edges. Equal-cost alternatives do not enqueue, so zero-cost cycles cannot loop indefinitely. A finalized cost cannot later decrease.
input
{"n":4,"edges":[[0,1,1],[0,2,0],[2,1,0],[1,2,0]],"source":0}
rows
0
cols
0
distance
[0,0,0,null]
frontier
[[1,1]]
settled
[0,2,1]
phase
"settle"
current
1
cost
0
Relax and place a strict improvement at the correct deque end.
A failed relaxation leaves both label and frontier unchanged. Weight zero goes to the front; weight one goes to the back. Stale snapshots remain until popped.
input
{"n":4,"edges":[[0,1,1],[0,2,0],[2,1,0],[1,2,0]],"source":0}
rows
0
cols
0
distance
[0,0,0,null]
frontier
[[1,1]]
settled
[0,2,1]
phase
"relax"
current
1
cost
0
edgeIndex
0
next
2
weight
0
candidate
0
improved
false
Discard an obsolete cost snapshot.
Compare the stored snapshot with the current label before scanning outgoing edges. Equal-cost alternatives do not enqueue, so zero-cost cycles cannot loop indefinitely. A finalized cost cannot later decrease.
input
{"n":4,"edges":[[0,1,1],[0,2,0],[2,1,0],[1,2,0]],"source":0}
rows
0
cols
0
distance
[0,0,0,null]
frontier
[]
settled
[0,2,1]
phase
"stale"
current
1
cost
1
Finish after the frontier is exhausted.
Unreachable labels remain infinite internally; the API uses −1. Network delay is the maximum shortest distance only when every declared vertex is reachable. Empty grid effort is zero.
input
{"n":4,"edges":[[0,1,1],[0,2,0],[2,1,0],[1,2,0]],"source":0}
rows
0
cols
0
distance
[0,0,0,null]
frontier
[]
settled
[0,2,1]
phase
"complete"
current
null
Return the documented result without changing caller input.
Static states and logical pictures are teaching histories, excluded from Java workspace. The result uses long arithmetic; shown fixture numbers are exact within JavaScript’s safe integer range.
result
[0,0,0,-1]

Zero cycle and a final positive edge

Input: {"n":3,"edges":[[0,1,0],[1,0,0],[1,1,0],[1,2,1]],"source":0} · Fresh binary shortest distances: [0,0,1]

Step 1 of 10: Seed a cost-zero snapshot for the source.

Binary weights — exact deque order and cost snapshots

Phase: initial.

Source: 0. Every label 0..2 exists; edge direction matters.

Directed edge occurrences — from → to : weight

0: 0 → 1 : 0
1: 1 → 0 : 0
2: 1 → 1 : 0
3: 1 → 2 : 1

Vertex arrival costs — tentative and final are separate

vertex 0cost: 0tentative
vertex 1cost: ∞ (no finite label)not reached
vertex 2cost: ∞ (no finite label)not reached

Deque — exact front → back snapshot order

0: [cost 0, vertex 0]

Only binary weights support this two-level deque ordering. Strict improvements stop equal-cost cycles from re-enqueueing forever.

State after this step
Variable	Value
input	`{"n":3,"edges":[[0,1,0],[1,0,0],[1,1,0],[1,2,1]],"source":0}`
rows	`0`
cols	`0`
distance	`[0,null,null]`
frontier	`[[0,0]]`
settled	`[]`
phase	`"initial"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static void validate(int n,int[][] edges,int source) {
 4         Objects.requireNonNull(edges,"edges");
 5         if(n<1||source<0||source>=n)throw new IllegalArgumentException("invalid universe or source");
 6         for(int[] e:edges)if(e==null||e.length!=3||e[0]<0||e[0]>=n||e[1]<0||e[1]>=n||e[2]<0||e[2]>1)throw new IllegalArgumentException("invalid weighted edge");
 7     }
 8     private record Entry(long cost,int vertex) {}
 9     private static final Comparator<Entry> ORDER=Comparator.comparingLong(Entry::cost).thenComparingInt(Entry::vertex);
10     private static List<List<int[]>> graph(int n,int[][] edges) {
11         List<List<int[]>> graph=new ArrayList<>();for(int v=0;v<n;v++)graph.add(new ArrayList<>());
12         for(int[] e:edges)graph.get(e[0]).add(new int[]{e[1],e[2]});return graph;
13     }
14     public static long[] binaryDistances(int n,int[][] edges,int source) {
15         validate(n,edges,source);var graph=graph(n,edges);long[] distance=new long[n];Arrays.fill(distance,Long.MAX_VALUE);distance[source]=0;
16         ArrayDeque<Entry> deque=new ArrayDeque<>();deque.addFirst(new Entry(0,source));
17         while(!deque.isEmpty()) {
18             Entry current=deque.removeFirst();int v=current.vertex();
19             if(current.cost()!=distance[v])continue;
20             for(int[] edge:graph.get(v)) {
21                 int next=edge[0];long candidate=current.cost()+edge[1];
22                 if(candidate<distance[next]) {
23                     distance[next]=candidate;Entry entry=new Entry(candidate,next);
24                     if(edge[1]==0)deque.addFirst(entry);else deque.addLast(entry);
25                 }
26             }
27         }
28         for(int v=0;v<n;v++)if(distance[v]==Long.MAX_VALUE)distance[v]=-1;return distance;
29     }
30     public static long[] baseline(int n,int[][] edges,int source) {
31         validate(n,edges,source);var graph=graph(n,edges);long[] d=new long[n];Arrays.fill(d,Long.MAX_VALUE);d[source]=0;PriorityQueue<Entry> q=new PriorityQueue<>(ORDER);q.add(new Entry(0,source));
32         while(!q.isEmpty()){Entry e=q.remove();if(e.cost()!=d[e.vertex()])continue;for(int[] edge:graph.get(e.vertex())){long candidate=e.cost()+edge[1];if(candidate<d[edge[0]]){d[edge[0]]=candidate;q.add(new Entry(candidate,edge[0]));}}}
33         for(int v=0;v<n;v++)if(d[v]==Long.MAX_VALUE)d[v]=-1;return d;
34     }
35 }
36

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Seed a cost-zero snapshot for the source.
Distances are tentative; null is infinity, represented by Long.MAX_VALUE in Java. Frontier pairs are [cost snapshot, vertex]. Heap pairs are shown in sorted removal order; deque pairs are exact front-to-back order.
input
{"n":3,"edges":[[0,1,0],[1,0,0],[1,1,0],[1,2,1]],"source":0}
rows
0
cols
0
distance
[0,null,null]
frontier
[[0,0]]
settled
[]
phase
"initial"
current
null
Remove the least valid cost and finalize this vertex.
Compare the stored snapshot with the current label before scanning outgoing edges. Equal-cost alternatives do not enqueue, so zero-cost cycles cannot loop indefinitely. A finalized cost cannot later decrease.
input
{"n":3,"edges":[[0,1,0],[1,0,0],[1,1,0],[1,2,1]],"source":0}
rows
0
cols
0
distance
[0,null,null]
frontier
[]
settled
[0]
phase
"settle"
current
0
cost
0
Relax and place a strict improvement at the correct deque end.
A failed relaxation leaves both label and frontier unchanged. Weight zero goes to the front; weight one goes to the back. Stale snapshots remain until popped.
input
{"n":3,"edges":[[0,1,0],[1,0,0],[1,1,0],[1,2,1]],"source":0}
rows
0
cols
0
distance
[0,0,null]
frontier
[[0,1]]
settled
[0]
phase
"relax"
current
0
cost
0
edgeIndex
0
next
1
weight
0
candidate
0
improved
true
Remove the least valid cost and finalize this vertex.
Compare the stored snapshot with the current label before scanning outgoing edges. Equal-cost alternatives do not enqueue, so zero-cost cycles cannot loop indefinitely. A finalized cost cannot later decrease.
input
{"n":3,"edges":[[0,1,0],[1,0,0],[1,1,0],[1,2,1]],"source":0}
rows
0
cols
0
distance
[0,0,null]
frontier
[]
settled
[0,1]
phase
"settle"
current
1
cost
0
Relax and place a strict improvement at the correct deque end.
A failed relaxation leaves both label and frontier unchanged. Weight zero goes to the front; weight one goes to the back. Stale snapshots remain until popped.
input
{"n":3,"edges":[[0,1,0],[1,0,0],[1,1,0],[1,2,1]],"source":0}
rows
0
cols
0
distance
[0,0,null]
frontier
[]
settled
[0,1]
phase
"relax"
current
1
cost
0
edgeIndex
0
next
0
weight
0
candidate
0
improved
false
Relax and place a strict improvement at the correct deque end.
A failed relaxation leaves both label and frontier unchanged. Weight zero goes to the front; weight one goes to the back. Stale snapshots remain until popped.
input
{"n":3,"edges":[[0,1,0],[1,0,0],[1,1,0],[1,2,1]],"source":0}
rows
0
cols
0
distance
[0,0,null]
frontier
[]
settled
[0,1]
phase
"relax"
current
1
cost
0
edgeIndex
1
next
1
weight
0
candidate
0
improved
false
Relax and place a strict improvement at the correct deque end.
A failed relaxation leaves both label and frontier unchanged. Weight zero goes to the front; weight one goes to the back. Stale snapshots remain until popped.
input
{"n":3,"edges":[[0,1,0],[1,0,0],[1,1,0],[1,2,1]],"source":0}
rows
0
cols
0
distance
[0,0,1]
frontier
[[1,2]]
settled
[0,1]
phase
"relax"
current
1
cost
0
edgeIndex
2
next
2
weight
1
candidate
1
improved
true
Remove the least valid cost and finalize this vertex.
Compare the stored snapshot with the current label before scanning outgoing edges. Equal-cost alternatives do not enqueue, so zero-cost cycles cannot loop indefinitely. A finalized cost cannot later decrease.
input
{"n":3,"edges":[[0,1,0],[1,0,0],[1,1,0],[1,2,1]],"source":0}
rows
0
cols
0
distance
[0,0,1]
frontier
[]
settled
[0,1,2]
phase
"settle"
current
2
cost
1
Finish after the frontier is exhausted.
Unreachable labels remain infinite internally; the API uses −1. Network delay is the maximum shortest distance only when every declared vertex is reachable. Empty grid effort is zero.
input
{"n":3,"edges":[[0,1,0],[1,0,0],[1,1,0],[1,2,1]],"source":0}
rows
0
cols
0
distance
[0,0,1]
frontier
[]
settled
[0,1,2]
phase
"complete"
current
null
Return the documented result without changing caller input.
Static states and logical pictures are teaching histories, excluded from Java workspace. The result uses long arithmetic; shown fixture numbers are exact within JavaScript’s safe integer range.
result
[0,0,1]

No outgoing edges leaves declared isolates

Input: {"n":3,"edges":[],"source":1} · Fresh binary shortest distances: [-1,0,-1]

Step 1 of 4: Seed a cost-zero snapshot for the source.

Binary weights — exact deque order and cost snapshots

Phase: initial.

Source: 1. Every label 0..2 exists; edge direction matters.

Directed edge occurrences — from → to : weight

Empty.

Vertex arrival costs — tentative and final are separate

vertex 0cost: ∞ (no finite label)not reached
vertex 1cost: 0tentative
vertex 2cost: ∞ (no finite label)not reached

Deque — exact front → back snapshot order

0: [cost 0, vertex 1]

Only binary weights support this two-level deque ordering. Strict improvements stop equal-cost cycles from re-enqueueing forever.

State after this step
Variable	Value
input	`{"n":3,"edges":[],"source":1}`
rows	`0`
cols	`0`
distance	`[null,0,null]`
frontier	`[[0,1]]`
settled	`[]`
phase	`"initial"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static void validate(int n,int[][] edges,int source) {
 4         Objects.requireNonNull(edges,"edges");
 5         if(n<1||source<0||source>=n)throw new IllegalArgumentException("invalid universe or source");
 6         for(int[] e:edges)if(e==null||e.length!=3||e[0]<0||e[0]>=n||e[1]<0||e[1]>=n||e[2]<0||e[2]>1)throw new IllegalArgumentException("invalid weighted edge");
 7     }
 8     private record Entry(long cost,int vertex) {}
 9     private static final Comparator<Entry> ORDER=Comparator.comparingLong(Entry::cost).thenComparingInt(Entry::vertex);
10     private static List<List<int[]>> graph(int n,int[][] edges) {
11         List<List<int[]>> graph=new ArrayList<>();for(int v=0;v<n;v++)graph.add(new ArrayList<>());
12         for(int[] e:edges)graph.get(e[0]).add(new int[]{e[1],e[2]});return graph;
13     }
14     public static long[] binaryDistances(int n,int[][] edges,int source) {
15         validate(n,edges,source);var graph=graph(n,edges);long[] distance=new long[n];Arrays.fill(distance,Long.MAX_VALUE);distance[source]=0;
16         ArrayDeque<Entry> deque=new ArrayDeque<>();deque.addFirst(new Entry(0,source));
17         while(!deque.isEmpty()) {
18             Entry current=deque.removeFirst();int v=current.vertex();
19             if(current.cost()!=distance[v])continue;
20             for(int[] edge:graph.get(v)) {
21                 int next=edge[0];long candidate=current.cost()+edge[1];
22                 if(candidate<distance[next]) {
23                     distance[next]=candidate;Entry entry=new Entry(candidate,next);
24                     if(edge[1]==0)deque.addFirst(entry);else deque.addLast(entry);
25                 }
26             }
27         }
28         for(int v=0;v<n;v++)if(distance[v]==Long.MAX_VALUE)distance[v]=-1;return distance;
29     }
30     public static long[] baseline(int n,int[][] edges,int source) {
31         validate(n,edges,source);var graph=graph(n,edges);long[] d=new long[n];Arrays.fill(d,Long.MAX_VALUE);d[source]=0;PriorityQueue<Entry> q=new PriorityQueue<>(ORDER);q.add(new Entry(0,source));
32         while(!q.isEmpty()){Entry e=q.remove();if(e.cost()!=d[e.vertex()])continue;for(int[] edge:graph.get(e.vertex())){long candidate=e.cost()+edge[1];if(candidate<d[edge[0]]){d[edge[0]]=candidate;q.add(new Entry(candidate,edge[0]));}}}
33         for(int v=0;v<n;v++)if(d[v]==Long.MAX_VALUE)d[v]=-1;return d;
34     }
35 }
36

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Seed a cost-zero snapshot for the source.
Distances are tentative; null is infinity, represented by Long.MAX_VALUE in Java. Frontier pairs are [cost snapshot, vertex]. Heap pairs are shown in sorted removal order; deque pairs are exact front-to-back order.
input
{"n":3,"edges":[],"source":1}
rows
0
cols
0
distance
[null,0,null]
frontier
[[0,1]]
settled
[]
phase
"initial"
current
null
Remove the least valid cost and finalize this vertex.
Compare the stored snapshot with the current label before scanning outgoing edges. Equal-cost alternatives do not enqueue, so zero-cost cycles cannot loop indefinitely. A finalized cost cannot later decrease.
input
{"n":3,"edges":[],"source":1}
rows
0
cols
0
distance
[null,0,null]
frontier
[]
settled
[1]
phase
"settle"
current
1
cost
0
Finish after the frontier is exhausted.
Unreachable labels remain infinite internally; the API uses −1. Network delay is the maximum shortest distance only when every declared vertex is reachable. Empty grid effort is zero.
input
{"n":3,"edges":[],"source":1}
rows
0
cols
0
distance
[null,0,null]
frontier
[]
settled
[1]
phase
"complete"
current
null
Return the documented result without changing caller input.
Static states and logical pictures are teaching histories, excluded from Java workspace. The result uses long arithmetic; shown fixture numbers are exact within JavaScript’s safe integer range.
result
[-1,0,-1]

Test the contract

Input: Cost-one discovery later improves to zero
Output: [0,0,0,…]
Exercises front insertion and stale rejection.
Input: Zero self-loop, zero cycle, parallel occurrences
Output: finite correct distances
Strict improvement prevents equal-cost loops.
Input: Disconnected declared vertex
Output: −1 at its position
The result covers the entire universe.
Input: 100,000-vertex one-edge-cost corridor
Output: distance[v]=v
Checks iterative linear traversal.
Input: Repeated calls and shared source rows
Output: fresh equal arrays; source unchanged
Output and input ownership are verified.

Common mistakes and counterexamples

Use hop-count BFS

Counterexample: 0→1 costs one while 0→2→1 costs zero.

Order work by cost using zero-front and one-back insertions.

Freeze a vertex on enqueue

Counterexample: The initial cost-one discovery of vertex one is not optimal.

Accept strict decreases until a valid minimum snapshot is popped.

Enqueue equal candidates

Counterexample: A zero-cost self-loop would keep proposing the same value.

Use strict less-than and discard stale snapshots.

Accept weight two

Counterexample: The deque’s two-level ordering proof no longer follows.

Validate every weight; use general Dijkstra for arbitrary nonnegative costs.

Follow-ups

Return a minimum-cost route.

Record predecessors on strict improvements. Define tie behavior carefully around zero cycles; equal-distance rewrites are unnecessary and can make reconstruction cyclic. Return vertices or edge occurrences according to the required witness.

Use small integer weights 0..C.

Consider cyclic buckets such as Dial’s algorithm, but derive bucket range, extraction rules, and O(E+CV)-style bounds. Simply sending every positive weight to the back breaks the binary ordering invariant.

Minimize edge reversals.

Create a zero-cost arc for following an original directed edge and a one-cost arc for traversing it backward. Then binary shortest cost counts reversals. Keep edge-occurrence identity if a reconstruction must distinguish parallel choices.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 196/20,000 characters

Self-review

Can I state the ordering invariant for stored snapshot costs, including stale entries?Can I justify O(V+E) despite duplicate proposals?Can I show why binary weights and strict relaxation are essential?

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Standard names do not imply company-frequency or external-platform parity claims.