Workspace Code & DSA
Learning pathsPricingA
← DSA problem library

DSA-113 · Nonnegative single-source shortest paths with lazy priority-queue snapshots

Network Delay Time

Intermediate · Java 21 · Version 1 · editorial draft

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

Understand the problem

Starting at source at time zero, a signal traverses directed edges taking their nonnegative weights in time units. Return the earliest time when all n vertices have received it, or −1 if any vertex is unreachable.

  • 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. Weights span 0..Integer.MAX_VALUE. Size preconditions: n≤100,000 and at most 200,000 edge occurrences.
  • networkDelay(n,edges,source) returns long. This teaching API uses zero-based labels rather than one-based labels. The source receives the signal immediately. For n=1, the answer is zero, even with no edges. Unreachable is −1, which cannot collide with a valid nonnegative answer. Distances and candidates fit long under the size preconditions.
  • 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.

Examples

  1. Input: n=4, edges=[[0,1,9],[0,2,1],[2,1,1],[1,3,0]], source=0
    Output: 2

    Shortest distances are [0,2,1,2]. The direct cost-nine discovery for vertex one becomes stale.

  2. Input: n=3, edges=[[0,1,4]], source=0
    Output: −1

    Vertex two belongs to the declared universe despite not appearing in an edge.

  3. Input: n=3, edges=[[0,1,MAX],[1,2,MAX]], source=0
    Output: 4294967294

    The sum exceeds int; casting only after addition would be too late.

Before you start

  • Directed weighted adjacency lists and strict relaxation
  • Minimum-priority queues, stale snapshots, and long arithmetic

Recognize the structure

Different edge times invalidate ordinary FIFO BFS: the earliest discovered route need not be the quickest. The requirement is one source to every vertex, followed by a maximum over shortest distances. Nonnegative weights make a minimum tentative label safe to finalize. A minimum spanning tree would optimize a different total and can give the wrong arrival times.

Try before revealing

Hint 1

What value does each vertex need before you can compute the overall delay?

Hint 2

Nonnegative weights let the minimum tentative label become final.

Hint 3

Use immutable heap snapshots, skip stale costs, relax strictly, then take the maximum or return −1.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Frozen Bellman–Ford rounds

Start with distance[source]=0 and all others infinite. In each of at most n−1 rounds clone the previous distances and relax every edge using only the old array. Round r accounts for paths with at most r edges. A nonnegative shortest walk can discard cycles, so a simple path suffices. Stop when a full round changes nothing. This compiling baseline provides a useful recurrence but scans the full edge list repeatedly.

Improve the baseline

Store tentative upper bounds

Each finite distance is the cost of some discovered route, not a promise that the first route was optimal. Build outgoing lists in input occurrence order. Seed only the source; do not give disconnected vertices zero.

Replace decrease-key with new snapshots

Java PriorityQueue does not support efficient indexed decrease-key here. Insert a new Entry(candidate,next) whenever a strict improvement occurs. The old entry remains in the heap. Sort by long cost, then vertex ID using comparator combinators rather than subtracting costs.

Finalize only a current minimum

Remove an entry and compare its stored cost with distance[v]. A mismatch is stale and must skip the adjacency scan. Otherwise nonnegative extensions cannot produce a cheaper route back to v. Relax each outgoing occurrence and, after exhaustion, return −1 for any infinity or the maximum finite distance.

Why it is correct

Route witnesses

Initially the source’s zero witnesses an empty path. Every accepted relaxation appends one real directed edge to a witnessed path, so labels never underestimate the true optimum. Infinity makes no reachability claim.

Minimum-label finality

Suppose a valid minimum pop v had a cheaper route. On that route take the first vertex outside the finalized set. Its predecessor was finalized and would have installed a tentative value no greater than that cheaper route’s total, because remaining weights are nonnegative. That entry would precede v, a contradiction. Zero weights preserve the non-strict inequality.

From distances to delay

Every reachable vertex eventually obtains a finite candidate and a valid pop. Stale pops add no new reasoning. Each individual earliest arrival equals its shortest distance; all arrivals have occurred precisely by their maximum. An unreachable declared vertex never receives the signal, so no finite common completion time exists.

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)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 networkDelay(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;
        PriorityQueue<Entry> heap=new PriorityQueue<>(ORDER);heap.add(new Entry(0,source));
        while(!heap.isEmpty()) {
            Entry current=heap.remove();int v=current.vertex();
            if(current.cost()!=distance[v])continue;
            for(int[] edge:graph.get(v)) {
                long candidate=current.cost()+edge[1];int next=edge[0];
                if(candidate<distance[next]) {distance[next]=candidate;heap.add(new Entry(candidate,next));}
            }
        }
        long answer=0;for(long cost:distance){if(cost==Long.MAX_VALUE)return -1;answer=Math.max(answer,cost);}return answer;
    }
    public static long baseline(int n,int[][] edges,int source) {
        validate(n,edges,source);long[] d=new long[n];Arrays.fill(d,Long.MAX_VALUE);d[source]=0;
        for(int pass=1;pass<n;pass++){long[] next=d.clone();for(int[] e:edges)if(d[e[0]]!=Long.MAX_VALUE)next[e[1]]=Math.min(next[e[1]],d[e[0]]+e[2]);if(Arrays.equals(d,next))break;d=next;}
        long answer=0;for(long cost:d){if(cost==Long.MAX_VALUE)return -1;answer=Math.max(answer,cost);}return answer;
    }
}

Read the meaningful blocks

The heap stores immutable proposals

Entry.cost is the value at insertion. Never compare two heap entries by consulting a mutable distance array: changing a key behind PriorityQueue would invalidate heap order. The walkthrough shows sorted removal order, not the queue’s internal array or iterator order.

Guard infinity before arithmetic

Only finite popped entries are scanned. current.cost()+edge[1] is long addition because current.cost is long. Long.MAX_VALUE is a sentinel, never a path operand. With at most 99,999 edges in a simple shortest path, full-int weights stay well below long overflow.

Strict improvements control duplicates

Use candidate<distance[next]. Equal routes need no second proposal. A zero self-loop or zero-cost directed cycle therefore cannot create endless equal-cost insertions. Validation still examines all triples before the algorithm starts.

Complexity

Let V=n and E be edge occurrences. Validation and adjacency construction take O(V+E). Each vertex has one valid pop; each outgoing occurrence is scanned once, and at most E strict relaxations insert entries. Main time is O(V+E+(E+1)log(E+2)); heap size can be O(E+1) with parallel edges, so do not silently replace log E by log V for arbitrary multigraphs. Auxiliary storage is O(V+E); output is one long.

The frozen baseline takes O(V+E+(V−1)(V+E)) worst-case time, including per-round array clones, and O(V) auxiliary space without adjacency lists. Early stability reduces actual rounds. Trace histories and sorted heap pictures are explanatory output, not stored by Java.

Exact-state walkthroughs

Reveal normal and boundary traces

A cheaper detour replaces an old heap proposal

Input: {"n":4,"edges":[[0,1,9],[0,2,1],[2,1,1],[1,3,0]],"source":0} · All-vertex arrival time / −1: 2

Step 1 of 12: 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.

Network delay — finalized arrivals and pending proposals

Phase: initial.

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

Directed edge occurrences — from → to : weight

  • 0: 0 → 1 : 9
  • 1: 0 → 2 : 1
  • 2: 2 → 1 : 1
  • 3: 1 → 3 : 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

Heap proposals — sorted removal order, not internal array order

  • 0: [cost 0, vertex 0]

Cost snapshots are immutable; improved labels leave older proposals to be discarded later. 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
VariableValue
input{"n":4,"edges":[[0,1,9],[0,2,1],[2,1,1],[1,3,0]],"source":0}
rows0
cols0
distance[0,null,null,null]
frontier[[0,0]]
settled[]
phase"initial"
currentnull
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)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 networkDelay(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         PriorityQueue<Entry> heap=new PriorityQueue<>(ORDER);heap.add(new Entry(0,source));
17         while(!heap.isEmpty()) {
18             Entry current=heap.remove();int v=current.vertex();
19             if(current.cost()!=distance[v])continue;
20             for(int[] edge:graph.get(v)) {
21                 long candidate=current.cost()+edge[1];int next=edge[0];
22                 if(candidate<distance[next]) {distance[next]=candidate;heap.add(new Entry(candidate,next));}
23             }
24         }
25         long answer=0;for(long cost:distance){if(cost==Long.MAX_VALUE)return -1;answer=Math.max(answer,cost);}return answer;
26     }
27     public static long baseline(int n,int[][] edges,int source) {
28         validate(n,edges,source);long[] d=new long[n];Arrays.fill(d,Long.MAX_VALUE);d[source]=0;
29         for(int pass=1;pass<n;pass++){long[] next=d.clone();for(int[] e:edges)if(d[e[0]]!=Long.MAX_VALUE)next[e[1]]=Math.min(next[e[1]],d[e[0]]+e[2]);if(Arrays.equals(d,next))break;d=next;}
30         long answer=0;for(long cost:d){if(cost==Long.MAX_VALUE)return -1;answer=Math.max(answer,cost);}return answer;
31     }
32 }
33

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

Read the full static trace
  1. 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,9],[0,2,1],[2,1,1],[1,3,0]],"source":0}
    rows
    0
    cols
    0
    distance
    [0,null,null,null]
    frontier
    [[0,0]]
    settled
    []
    phase
    "initial"
    current
    null
  2. 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,9],[0,2,1],[2,1,1],[1,3,0]],"source":0}
    rows
    0
    cols
    0
    distance
    [0,null,null,null]
    frontier
    []
    settled
    [0]
    phase
    "settle"
    current
    0
    cost
    0
  3. Relax one outgoing directed occurrence.

    A failed relaxation leaves both label and frontier unchanged. The candidate adds a nonnegative weight to an already finalized distance.

    input
    {"n":4,"edges":[[0,1,9],[0,2,1],[2,1,1],[1,3,0]],"source":0}
    rows
    0
    cols
    0
    distance
    [0,9,null,null]
    frontier
    [[9,1]]
    settled
    [0]
    phase
    "relax"
    current
    0
    cost
    0
    edgeIndex
    0
    next
    1
    weight
    9
    candidate
    9
    improved
    true
  4. Relax one outgoing directed occurrence.

    A failed relaxation leaves both label and frontier unchanged. The candidate adds a nonnegative weight to an already finalized distance.

    input
    {"n":4,"edges":[[0,1,9],[0,2,1],[2,1,1],[1,3,0]],"source":0}
    rows
    0
    cols
    0
    distance
    [0,9,1,null]
    frontier
    [[1,2],[9,1]]
    settled
    [0]
    phase
    "relax"
    current
    0
    cost
    0
    edgeIndex
    1
    next
    2
    weight
    1
    candidate
    1
    improved
    true
  5. 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,9],[0,2,1],[2,1,1],[1,3,0]],"source":0}
    rows
    0
    cols
    0
    distance
    [0,9,1,null]
    frontier
    [[9,1]]
    settled
    [0,2]
    phase
    "settle"
    current
    2
    cost
    1
  6. Relax one outgoing directed occurrence.

    A failed relaxation leaves both label and frontier unchanged. The candidate adds a nonnegative weight to an already finalized distance.

    input
    {"n":4,"edges":[[0,1,9],[0,2,1],[2,1,1],[1,3,0]],"source":0}
    rows
    0
    cols
    0
    distance
    [0,2,1,null]
    frontier
    [[2,1],[9,1]]
    settled
    [0,2]
    phase
    "relax"
    current
    2
    cost
    1
    edgeIndex
    0
    next
    1
    weight
    1
    candidate
    2
    improved
    true
  7. 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,9],[0,2,1],[2,1,1],[1,3,0]],"source":0}
    rows
    0
    cols
    0
    distance
    [0,2,1,null]
    frontier
    [[9,1]]
    settled
    [0,2,1]
    phase
    "settle"
    current
    1
    cost
    2
  8. Relax one outgoing directed occurrence.

    A failed relaxation leaves both label and frontier unchanged. The candidate adds a nonnegative weight to an already finalized distance.

    input
    {"n":4,"edges":[[0,1,9],[0,2,1],[2,1,1],[1,3,0]],"source":0}
    rows
    0
    cols
    0
    distance
    [0,2,1,2]
    frontier
    [[2,3],[9,1]]
    settled
    [0,2,1]
    phase
    "relax"
    current
    1
    cost
    2
    edgeIndex
    0
    next
    3
    weight
    0
    candidate
    2
    improved
    true
  9. 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,9],[0,2,1],[2,1,1],[1,3,0]],"source":0}
    rows
    0
    cols
    0
    distance
    [0,2,1,2]
    frontier
    [[9,1]]
    settled
    [0,2,1,3]
    phase
    "settle"
    current
    3
    cost
    2
  10. 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,9],[0,2,1],[2,1,1],[1,3,0]],"source":0}
    rows
    0
    cols
    0
    distance
    [0,2,1,2]
    frontier
    []
    settled
    [0,2,1,3]
    phase
    "stale"
    current
    1
    cost
    9
  11. 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,9],[0,2,1],[2,1,1],[1,3,0]],"source":0}
    rows
    0
    cols
    0
    distance
    [0,2,1,2]
    frontier
    []
    settled
    [0,2,1,3]
    phase
    "complete"
    current
    null
  12. 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
    2

A declared isolated vertex prevents complete arrival

Input: {"n":3,"edges":[[0,1,4]],"source":0} · All-vertex arrival time / −1: -1

Step 1 of 6: 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.

Network delay — finalized arrivals and pending proposals

Phase: initial.

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

Directed edge occurrences — from → to : weight

  • 0: 0 → 1 : 4

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

Heap proposals — sorted removal order, not internal array order

  • 0: [cost 0, vertex 0]

Cost snapshots are immutable; improved labels leave older proposals to be discarded later. 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
VariableValue
input{"n":3,"edges":[[0,1,4]],"source":0}
rows0
cols0
distance[0,null,null]
frontier[[0,0]]
settled[]
phase"initial"
currentnull
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)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 networkDelay(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         PriorityQueue<Entry> heap=new PriorityQueue<>(ORDER);heap.add(new Entry(0,source));
17         while(!heap.isEmpty()) {
18             Entry current=heap.remove();int v=current.vertex();
19             if(current.cost()!=distance[v])continue;
20             for(int[] edge:graph.get(v)) {
21                 long candidate=current.cost()+edge[1];int next=edge[0];
22                 if(candidate<distance[next]) {distance[next]=candidate;heap.add(new Entry(candidate,next));}
23             }
24         }
25         long answer=0;for(long cost:distance){if(cost==Long.MAX_VALUE)return -1;answer=Math.max(answer,cost);}return answer;
26     }
27     public static long baseline(int n,int[][] edges,int source) {
28         validate(n,edges,source);long[] d=new long[n];Arrays.fill(d,Long.MAX_VALUE);d[source]=0;
29         for(int pass=1;pass<n;pass++){long[] next=d.clone();for(int[] e:edges)if(d[e[0]]!=Long.MAX_VALUE)next[e[1]]=Math.min(next[e[1]],d[e[0]]+e[2]);if(Arrays.equals(d,next))break;d=next;}
30         long answer=0;for(long cost:d){if(cost==Long.MAX_VALUE)return -1;answer=Math.max(answer,cost);}return answer;
31     }
32 }
33

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

Read the full static trace
  1. 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,4]],"source":0}
    rows
    0
    cols
    0
    distance
    [0,null,null]
    frontier
    [[0,0]]
    settled
    []
    phase
    "initial"
    current
    null
  2. 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,4]],"source":0}
    rows
    0
    cols
    0
    distance
    [0,null,null]
    frontier
    []
    settled
    [0]
    phase
    "settle"
    current
    0
    cost
    0
  3. Relax one outgoing directed occurrence.

    A failed relaxation leaves both label and frontier unchanged. The candidate adds a nonnegative weight to an already finalized distance.

    input
    {"n":3,"edges":[[0,1,4]],"source":0}
    rows
    0
    cols
    0
    distance
    [0,4,null]
    frontier
    [[4,1]]
    settled
    [0]
    phase
    "relax"
    current
    0
    cost
    0
    edgeIndex
    0
    next
    1
    weight
    4
    candidate
    4
    improved
    true
  4. 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,4]],"source":0}
    rows
    0
    cols
    0
    distance
    [0,4,null]
    frontier
    []
    settled
    [0,1]
    phase
    "settle"
    current
    1
    cost
    4
  5. 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,4]],"source":0}
    rows
    0
    cols
    0
    distance
    [0,4,null]
    frontier
    []
    settled
    [0,1]
    phase
    "complete"
    current
    null
  6. 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

Zero cycle and duplicate occurrences

Input: {"n":3,"edges":[[0,1,0],[0,1,0],[1,0,0],[1,2,1]],"source":0} · All-vertex arrival time / −1: 1

Step 1 of 10: 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.

Network delay — finalized arrivals and pending proposals

Phase: initial.

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

Directed edge occurrences — from → to : weight

  • 0: 0 → 1 : 0
  • 1: 0 → 1 : 0
  • 2: 1 → 0 : 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

Heap proposals — sorted removal order, not internal array order

  • 0: [cost 0, vertex 0]

Cost snapshots are immutable; improved labels leave older proposals to be discarded later. 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
VariableValue
input{"n":3,"edges":[[0,1,0],[0,1,0],[1,0,0],[1,2,1]],"source":0}
rows0
cols0
distance[0,null,null]
frontier[[0,0]]
settled[]
phase"initial"
currentnull
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)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 networkDelay(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         PriorityQueue<Entry> heap=new PriorityQueue<>(ORDER);heap.add(new Entry(0,source));
17         while(!heap.isEmpty()) {
18             Entry current=heap.remove();int v=current.vertex();
19             if(current.cost()!=distance[v])continue;
20             for(int[] edge:graph.get(v)) {
21                 long candidate=current.cost()+edge[1];int next=edge[0];
22                 if(candidate<distance[next]) {distance[next]=candidate;heap.add(new Entry(candidate,next));}
23             }
24         }
25         long answer=0;for(long cost:distance){if(cost==Long.MAX_VALUE)return -1;answer=Math.max(answer,cost);}return answer;
26     }
27     public static long baseline(int n,int[][] edges,int source) {
28         validate(n,edges,source);long[] d=new long[n];Arrays.fill(d,Long.MAX_VALUE);d[source]=0;
29         for(int pass=1;pass<n;pass++){long[] next=d.clone();for(int[] e:edges)if(d[e[0]]!=Long.MAX_VALUE)next[e[1]]=Math.min(next[e[1]],d[e[0]]+e[2]);if(Arrays.equals(d,next))break;d=next;}
30         long answer=0;for(long cost:d){if(cost==Long.MAX_VALUE)return -1;answer=Math.max(answer,cost);}return answer;
31     }
32 }
33

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

Read the full static trace
  1. 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],[0,1,0],[1,0,0],[1,2,1]],"source":0}
    rows
    0
    cols
    0
    distance
    [0,null,null]
    frontier
    [[0,0]]
    settled
    []
    phase
    "initial"
    current
    null
  2. 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],[0,1,0],[1,0,0],[1,2,1]],"source":0}
    rows
    0
    cols
    0
    distance
    [0,null,null]
    frontier
    []
    settled
    [0]
    phase
    "settle"
    current
    0
    cost
    0
  3. Relax one outgoing directed occurrence.

    A failed relaxation leaves both label and frontier unchanged. The candidate adds a nonnegative weight to an already finalized distance.

    input
    {"n":3,"edges":[[0,1,0],[0,1,0],[1,0,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
  4. Relax one outgoing directed occurrence.

    A failed relaxation leaves both label and frontier unchanged. The candidate adds a nonnegative weight to an already finalized distance.

    input
    {"n":3,"edges":[[0,1,0],[0,1,0],[1,0,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
    1
    next
    1
    weight
    0
    candidate
    0
    improved
    false
  5. 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],[0,1,0],[1,0,0],[1,2,1]],"source":0}
    rows
    0
    cols
    0
    distance
    [0,0,null]
    frontier
    []
    settled
    [0,1]
    phase
    "settle"
    current
    1
    cost
    0
  6. Relax one outgoing directed occurrence.

    A failed relaxation leaves both label and frontier unchanged. The candidate adds a nonnegative weight to an already finalized distance.

    input
    {"n":3,"edges":[[0,1,0],[0,1,0],[1,0,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
  7. Relax one outgoing directed occurrence.

    A failed relaxation leaves both label and frontier unchanged. The candidate adds a nonnegative weight to an already finalized distance.

    input
    {"n":3,"edges":[[0,1,0],[0,1,0],[1,0,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
    1
    next
    2
    weight
    1
    candidate
    1
    improved
    true
  8. 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],[0,1,0],[1,0,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
  9. 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],[0,1,0],[1,0,0],[1,2,1]],"source":0}
    rows
    0
    cols
    0
    distance
    [0,0,1]
    frontier
    []
    settled
    [0,1,2]
    phase
    "complete"
    current
    null
  10. 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

Path sum beyond int

Input: {"n":3,"edges":[[0,1,2147483647],[1,2,2147483647]],"source":0} · All-vertex arrival time / −1: 4294967294

Step 1 of 8: 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.

Network delay — finalized arrivals and pending proposals

Phase: initial.

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

Directed edge occurrences — from → to : weight

  • 0: 0 → 1 : 2147483647
  • 1: 1 → 2 : 2147483647

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

Heap proposals — sorted removal order, not internal array order

  • 0: [cost 0, vertex 0]

Cost snapshots are immutable; improved labels leave older proposals to be discarded later. 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
VariableValue
input{"n":3,"edges":[[0,1,2147483647],[1,2,2147483647]],"source":0}
rows0
cols0
distance[0,null,null]
frontier[[0,0]]
settled[]
phase"initial"
currentnull
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)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 networkDelay(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         PriorityQueue<Entry> heap=new PriorityQueue<>(ORDER);heap.add(new Entry(0,source));
17         while(!heap.isEmpty()) {
18             Entry current=heap.remove();int v=current.vertex();
19             if(current.cost()!=distance[v])continue;
20             for(int[] edge:graph.get(v)) {
21                 long candidate=current.cost()+edge[1];int next=edge[0];
22                 if(candidate<distance[next]) {distance[next]=candidate;heap.add(new Entry(candidate,next));}
23             }
24         }
25         long answer=0;for(long cost:distance){if(cost==Long.MAX_VALUE)return -1;answer=Math.max(answer,cost);}return answer;
26     }
27     public static long baseline(int n,int[][] edges,int source) {
28         validate(n,edges,source);long[] d=new long[n];Arrays.fill(d,Long.MAX_VALUE);d[source]=0;
29         for(int pass=1;pass<n;pass++){long[] next=d.clone();for(int[] e:edges)if(d[e[0]]!=Long.MAX_VALUE)next[e[1]]=Math.min(next[e[1]],d[e[0]]+e[2]);if(Arrays.equals(d,next))break;d=next;}
30         long answer=0;for(long cost:d){if(cost==Long.MAX_VALUE)return -1;answer=Math.max(answer,cost);}return answer;
31     }
32 }
33

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

Read the full static trace
  1. 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,2147483647],[1,2,2147483647]],"source":0}
    rows
    0
    cols
    0
    distance
    [0,null,null]
    frontier
    [[0,0]]
    settled
    []
    phase
    "initial"
    current
    null
  2. 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,2147483647],[1,2,2147483647]],"source":0}
    rows
    0
    cols
    0
    distance
    [0,null,null]
    frontier
    []
    settled
    [0]
    phase
    "settle"
    current
    0
    cost
    0
  3. Relax one outgoing directed occurrence.

    A failed relaxation leaves both label and frontier unchanged. The candidate adds a nonnegative weight to an already finalized distance.

    input
    {"n":3,"edges":[[0,1,2147483647],[1,2,2147483647]],"source":0}
    rows
    0
    cols
    0
    distance
    [0,2147483647,null]
    frontier
    [[2147483647,1]]
    settled
    [0]
    phase
    "relax"
    current
    0
    cost
    0
    edgeIndex
    0
    next
    1
    weight
    2147483647
    candidate
    2147483647
    improved
    true
  4. 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,2147483647],[1,2,2147483647]],"source":0}
    rows
    0
    cols
    0
    distance
    [0,2147483647,null]
    frontier
    []
    settled
    [0,1]
    phase
    "settle"
    current
    1
    cost
    2147483647
  5. Relax one outgoing directed occurrence.

    A failed relaxation leaves both label and frontier unchanged. The candidate adds a nonnegative weight to an already finalized distance.

    input
    {"n":3,"edges":[[0,1,2147483647],[1,2,2147483647]],"source":0}
    rows
    0
    cols
    0
    distance
    [0,2147483647,4294967294]
    frontier
    [[4294967294,2]]
    settled
    [0,1]
    phase
    "relax"
    current
    1
    cost
    2147483647
    edgeIndex
    0
    next
    2
    weight
    2147483647
    candidate
    4294967294
    improved
    true
  6. 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,2147483647],[1,2,2147483647]],"source":0}
    rows
    0
    cols
    0
    distance
    [0,2147483647,4294967294]
    frontier
    []
    settled
    [0,1,2]
    phase
    "settle"
    current
    2
    cost
    4294967294
  7. 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,2147483647],[1,2,2147483647]],"source":0}
    rows
    0
    cols
    0
    distance
    [0,2147483647,4294967294]
    frontier
    []
    settled
    [0,1,2]
    phase
    "complete"
    current
    null
  8. 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
    4294967294

Test the contract

  1. Input: One vertex, no edges
    Output: 0

    The empty path reaches its source.

  2. Input: Directed edges toward the source only
    Output: −1 if another vertex is unreachable

    Connectivity must respect direction.

  3. Input: Parallel edges, zero cycle, stale proposal
    Output: minimum arrivals without repeated equal work

    Strict relaxation and snapshot checks handle all three.

  4. Input: 100,000-vertex MAX-weight corridor
    Output: 99999×MAX as long

    The harness checks large arithmetic and iterative traversal.

  5. Input: Shared rows and malformed triples
    Output: preserved input / documented exception

    Ownership and validation are part of the contract.

Common mistakes and counterexamples

Mark a vertex finished when first enqueued

Counterexample: 0→1 costs 9, but 0→2→1 costs 2.

Finalize on a valid minimum pop and accept later improvements while tentative.

Return the sum of distances

Counterexample: Distances [0,2,1,2] finish by time 2, not time 5.

Return the maximum shortest distance after checking every vertex is reachable.

Ignore stale entries or allow equal reinsertion

Counterexample: An obsolete cost-nine entry can rescan adjacency; zero cycles can repeatedly enqueue equal routes.

Skip snapshot mismatches and enqueue only strict improvements.

Add two ints before assigning to long

Counterexample: MAX+MAX wraps before a long receives it.

Keep the path prefix as long throughout the candidate calculation.

Follow-ups

Return one fastest route to each vertex.

Record a predecessor on strict improvement, then reconstruct a requested route. Define deterministic handling of equal-cost routes separately; blindly rewriting predecessors on ties can introduce cycles through zero-weight edges.

Allow negative transmission costs.

The finality proof fails. Bellman–Ford needs reachable negative-cycle detection and a clear meaning for an arrival time unbounded below; simply removing validation does not adapt Dijkstra.

Start from several simultaneous sources.

Seed each distinct valid source at zero. The same minimum-label proof computes distance to the closest source. Preserve the all-vertices reachability check and maximum aggregation.

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.

No unsaved text changes · 183/20,000 characters

Self-review

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.