BFS finds shortest paths only when every edge costs the same. The moment edges carry different weights, swap the queue for a heap. That one change is Dijkstra.
Breadth-first search works because it reaches nodes in order of hop count, and with equal edges hop count is distance. Give the edges weights and that breaks: two cheap hops can beat one expensive hop. This page covers the three tools that fix it, and when to reach for each: Dijkstra for non-negative weights, 0-1 BFS when every weight is 0 or 1, and Bellman-Ford for negative weights or a cap on the number of edges.
max in place of +.LinkedList<int>.Reading the figure. The left graph has one heavy edge, the red 5, and three edges of cost 1. The middle column is BFS order. It reaches A in one hop and reports 5, which is wrong. The right column is the heap in pop order. Green rows settle a node for good. The red row is the old entry for A. It pops last and the stale check skips it.
Lazy deletion. .NET’s PriorityQueue<TElement, TPriority> is a min-heap with no “decrease key” and no way to remove one entry. When a node’s distance improves, enqueue a second entry and leave the old one in the heap. When an entry comes off, compare it to the best distance on record. If it is larger, it is stale: skip it. The heap grows to O(E) entries, which costs only a constant factor, since log E ≤ 2 log V.
The C# heap API. Put the node in the element slot and the distance in the priority slot: heap.Enqueue(node, dist). Then heap.TryDequeue(out int node, out int d) hands back both in one call and ends the loop when the heap is empty. You never build a (dist, node) tuple the way Python does. When ties need a rule, make the priority a tuple such as (int Dist, int Node). Value tuples compare field by field.
Why negative edges break it. Dijkstra finalises a node on pop. A negative edge found later could make that node cheaper, and the algorithm never looks back. Bellman-Ford does look back: it relaxes every edge, round after round. After round i it knows every shortest path that uses at most i edges. That round count is also what makes it the right tool for “at most k stops”.
public static class Dijkstra
{
/// <summary>Shortest distance from source to every reachable node.</summary>
/// <param name="graph">Maps each node to a list of (To, Weight). Weights are 0 or more.</param>
/// <param name="source">The start node.</param>
/// <returns>A map of node to shortest distance, for reachable nodes only.</returns>
/// <example>
/// Distances({0: [(1, 4), (2, 1)], 2: [(1, 2)], 1: []}, 0) gives {0: 0, 1: 3, 2: 1}.
/// </example>
public static Dictionary<int, int> Distances(
Dictionary<int, List<(int To, int Weight)>> graph, int source)
{
// dist holds the best distance found so far. The source costs 0 to reach.
var dist = new Dictionary<int, int> { [source] = 0 };
// Element is the node, priority is its distance, so the smallest distance pops first.
var heap = new PriorityQueue<int, int>();
heap.Enqueue(source, 0); // 0: the source starts at distance 0
// Invariant: when an entry pops and is not stale, its distance is final.
while (heap.TryDequeue(out int node, out int d)) // cheapest tentative node left
{
if (d > dist[node]) // stale: a cheaper entry already won
continue;
// A node with no outgoing edges may be missing from graph. Skip it.
if (!graph.TryGetValue(node, out var edges))
continue;
// Relax: try to improve each neighbor by going through node.
foreach (var (neighbor, weight) in edges)
{
int candidate = d + weight; // cost to reach neighbor via node
// A missing key means never reached, which counts as infinitely far.
if (!dist.TryGetValue(neighbor, out int old) || candidate < old)
{
dist[neighbor] = candidate;
// Push a new entry. The old one stays and is skipped later.
heap.Enqueue(neighbor, candidate);
}
}
}
return dist;
}
}
The stale check d > dist[node] is the whole of lazy deletion. Without it the code is still correct, but it re-relaxes edges from old entries and can blow up to far more work. An equivalent form keeps a done HashSet<int> and skips any node already in it. Problem 1 uses that form.
Reading the figure. Each column is one pop, using the docstring graph. The amber box is the entry just popped. Blue boxes are live heap entries. A red entry is stale: dist already holds a smaller value for that node. Notice that (4, 1) turns red in step 2 but stays in the heap. Lazy deletion only drops it in step 4.
public static class ZeroOneBfs
{
/// <summary>Shortest distances when every edge weight is 0 or 1.</summary>
/// <param name="graph">Maps each node to a list of (To, Weight), weight 0 or 1.</param>
/// <param name="source">The start node.</param>
/// <returns>A map of node to shortest distance, for reachable nodes only.</returns>
/// <example>
/// Distances({0: [(1, 1), (2, 0)], 2: [(1, 0)], 1: []}, 0) gives {0: 0, 1: 0, 2: 0}.
/// </example>
public static Dictionary<int, int> Distances(
Dictionary<int, List<(int To, int Weight)>> graph, int source)
{
var dist = new Dictionary<int, int> { [source] = 0 }; // 0: the source is free
// .NET has no deque. LinkedList gives O(1) add and remove at both ends.
var queue = new LinkedList<int>();
queue.AddLast(source);
// Invariant: the list holds at most two distances, d at the front and
// d + 1 at the back, in that order. So the front is always a cheapest node.
while (queue.Count > 0) // 0: nothing left to settle
{
int node = queue.First!.Value; // take a cheapest node from the front
queue.RemoveFirst();
if (!graph.TryGetValue(node, out var edges)) // node with no edges
continue;
foreach (var (neighbor, weight) in edges)
{
int candidate = dist[node] + weight;
// A missing key means never reached, which counts as infinitely far.
if (!dist.TryGetValue(neighbor, out int old) || candidate < old)
{
dist[neighbor] = candidate;
if (weight == 0) // 0: same distance as node, so it goes first
queue.AddFirst(neighbor);
else // weight 1: one more, so it waits its turn
queue.AddLast(neighbor);
}
}
}
return dist;
}
}
.NET has no deque type. Queue<T> only adds at the back, so it cannot push a free edge to the front. LinkedList<int> has AddFirst, AddLast and RemoveFirst, all O(1). It allocates one node per push, which is fine at interview sizes. The deque plays the part of the heap. A free edge goes to the front, a paid edge to the back, so the deque stays sorted with no log factor. A node can be pushed twice if it improves. Re-processing it is harmless because a second pass finds nothing better. The classic use is LeetCode 1368, Minimum Cost to Make at Least One Valid Path in a Grid: following the arrow costs 0, changing it costs 1.
Reading the figure. Each row is one step on the docstring graph. Blue cells are queued nodes, front on the left. The red cell is an old copy of node 1, pushed when its distance was still 1. Notice that node 2 and the improved node 1 both enter at the front, because their edges cost 0. The old copy pops last and changes nothing.
public static class BellmanFord
{
/// <summary>Marks a node no path has reached yet.</summary>
public const int Unreached = int.MaxValue; // MaxValue: larger than any real cost
/// <summary>Cheapest cost to each node using at most maxEdges edges.</summary>
/// <param name="n">Number of nodes, labelled 0 to n - 1.</param>
/// <param name="edges">Directed (Start, End, Weight) triples. Weights may be negative.</param>
/// <param name="source">The start node.</param>
/// <param name="maxEdges">Most edges a path may use. Pass n - 1 for plain paths.</param>
/// <returns>An array of costs. Unreachable nodes hold <see cref="Unreached"/>.</returns>
/// <example>
/// Costs(3, [(0, 1, 4), (0, 2, 5), (2, 1, -3)], 0, 2) gives [0, 2, 5].
/// </example>
public static int[] Costs(
int n, (int Start, int End, int Weight)[] edges, int source, int maxEdges)
{
// n slots, one per node. Every node starts unreachable.
var cost = new int[n];
Array.Fill(cost, Unreached);
cost[source] = 0; // the source costs 0 to reach
// Loop variable counts passes. Each pass allows one more edge.
// Invariant: after pass i, cost[v] is the best path with at most i edges.
for (int pass = 0; pass < maxEdges; pass++) // 0: no edges used yet
{
var previous = (int[])cost.Clone(); // a copy, so this pass reads last pass only
foreach (var (start, end, weight) in edges)
{
// Skip unreached starts: Unreached + weight would overflow int.
if (previous[start] == Unreached)
continue;
// Extend a path from the LAST pass by exactly one edge.
if (previous[start] + weight < cost[end])
cost[end] = previous[start] + weight;
}
}
return cost;
}
}
C# has no float infinity for ints, so int.MaxValue plays that part as Unreached. Adding any positive weight to it overflows and wraps to a large negative number, so the code skips unreached starts before it adds. With maxEdges = n - 1 this is textbook Bellman-Ford: no simple path has more than n - 1 edges. Run one extra pass after that. If anything still improves, the graph has a negative cycle reachable from the source. When there is no edge limit you may drop the copy, which only speeds things up. With a limit, the copy is required. Problem 3 shows why.
Reading the figure. The graph is the docstring example. The red -3 is the negative edge. Each row is the cost array after one pass. inf stands for Unreached. Amber cells changed in that pass. The green cell is the improvement that needs two edges. With maxEdges = 1 you stop after round 1 and get 4.
if (d > dist[node]) continue;, old heap entries re-relax edges with wrong distances. The answer stays right but the work can explode.k + 1 edges. Say it out loud before you code the loop.int.MaxValue + w wraps negative and looks like a great path. Check for the sentinel first, or keep costs in long.heap.UnorderedItems gives heap order, not sorted order. Only Dequeue gives the minimum.A network has n nodes labelled 1 to n. times[i] = (u, v, w) means a signal takes w time to travel from u to v. A signal starts at node k. Return the time until every node has it, or -1 if some node never does.
k. Weights are non-negative, so this is Dijkstra.final.TryAdd does the check and the insert in one call.public static class NetworkDelay
{
/// <summary>Time for a signal from node k to reach every node, or -1.</summary>
/// <param name="times">Directed edges [u, v, w], travel time w is 0 or more.</param>
/// <param name="n">Number of nodes, labelled 1 to n.</param>
/// <param name="k">The node that sends the signal.</param>
/// <returns>The time when the last node hears the signal, or -1 if one never does.</returns>
/// <example>
/// NetworkDelayTime([[2, 1, 1], [2, 3, 1], [3, 4, 1]], 4, 2) returns 2.
/// </example>
public static int NetworkDelayTime(int[][] times, int n, int k)
{
// Adjacency list: graph[u] is a list of (v, w). n + 1 slots because labels
// run 1..n, so slot 0 is unused.
var graph = new List<(int To, int Delay)>[n + 1];
for (int u = 0; u <= n; u++) // 0..n: fill every slot so none is null
graph[u] = [];
foreach (var edge in times)
graph[edge[0]].Add((edge[1], edge[2])); // [0] from, [1] to, [2] time
var final = new Dictionary<int, int>(); // node to its settled shortest time
var heap = new PriorityQueue<int, int>(); // element node, priority time
heap.Enqueue(k, 0); // 0: the sender hears it at time 0
// Invariant: every node in final has its true shortest time.
while (heap.TryDequeue(out int node, out int time)) // earliest unsettled arrival
{
if (!final.TryAdd(node, time)) // already settled: this entry is stale
continue; // TryAdd: the first pop is the shortest time
foreach (var (neighbor, delay) in graph[node])
{
if (!final.ContainsKey(neighbor)) // settled nodes cannot improve
heap.Enqueue(neighbor, time + delay);
}
}
// Fewer than n settled means some node is unreachable, so -1 per the problem.
return final.Count == n ? final.Values.Max() : -1;
}
}
times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2:
(0, 2). Settle node 2 at 0. Push (1, 1) and (1, 3).(1, 1). Settle node 1 at 1. No edges out.(1, 3). Settle node 3 at 1. Push (2, 4).(2, 4). Settle node 4 at 2. Heap empty.Reading the figure. Every edge costs 1 here. In each frame the amber node has just popped and settled. Green nodes settled earlier. Blue nodes wait in the heap, and grey nodes are not yet found. The t= label is the settled time. The answer is the largest label once all four are green.
k: final.Count < n, return -1.n = 1: the sender is the only node, answer 0.n + 1 slots so label n fits, and slot 0 stays empty.You are given a grid of heights. You start at the top-left cell and want to reach the bottom-right, moving up, down, left or right. The effort of a route is the largest absolute height difference between two consecutive cells on it. Return the minimum effort.
max instead of +.max never makes a route cheaper as it grows, just as adding a non-negative weight never does. That is the only property Dijkstra needs.public static class MinimumEffort
{
// Four moves: down, up, right, left. Each is a (row change, col change).
private static readonly (int Dr, int Dc)[] Steps = [(1, 0), (-1, 0), (0, 1), (0, -1)];
/// <summary>Smallest possible largest step on a route from top-left to bottom-right.</summary>
/// <param name="heights">A non-empty grid of cell heights.</param>
/// <returns>The minimum effort over all routes.</returns>
/// <example>
/// MinimumEffortPath([[1, 2, 2], [3, 8, 2], [5, 3, 5]]) returns 2.
/// </example>
public static int MinimumEffortPath(int[][] heights)
{
int rows = heights.Length, cols = heights[0].Length; // [0]: any row gives the width
// best[r, c]: smallest effort found so far to reach (r, c). MaxValue means unseen.
var best = new int[rows, cols];
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
best[r, c] = int.MaxValue; // MaxValue: larger than any real effort
best[0, 0] = 0; // the start costs 0 effort: no steps yet
// Element is the cell, priority is the effort to reach it.
var heap = new PriorityQueue<(int R, int C), int>();
heap.Enqueue((0, 0), 0); // (0, 0): the start cell, effort 0
// Invariant: a non-stale pop carries the final effort for its cell.
while (heap.TryDequeue(out var cell, out int effort))
{
var (r, c) = cell;
if (effort > best[r, c]) // stale: a better entry already won
continue;
// - 1: last row and last column. Final on pop, so return now.
if (r == rows - 1 && c == cols - 1)
return effort;
foreach (var (dr, dc) in Steps)
{
int nr = r + dr, nc = c + dc;
// 0 is the first row or column. rows and cols are one past the last.
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols)
continue;
int climb = Math.Abs(heights[nr][nc] - heights[r][c]);
int candidate = Math.Max(effort, climb); // route effort is its worst step
if (candidate < best[nr, nc])
{
best[nr, nc] = candidate;
heap.Enqueue((nr, nc), candidate);
}
}
}
// Not reached: the target is always reachable. Kept as a safe fallback.
return best[rows - 1, cols - 1]; // - 1: index of the last row and column
}
}
heights = [[1,2,2],[3,8,2],[5,3,5]]:
(0, 0, 0). Push right (1, 0, 1) and down (2, 1, 0).(1, 0, 1). Push (1, 0, 2). Also push (6, 1, 1), the climb into the 8.(1, 0, 2). Push (1, 1, 2).(1, 1, 2). Step to (2,2) climbs 3, push (3, 2, 2).(2, 1, 0). Push (2, 2, 0). Pop it, push (2, 2, 1). Pop it, step to (2,2) climbs 2, push (2, 2, 2).(2, 2, 2). Target. Return 2, by the left column and bottom row.Reading the figure. On the left, green cells form the winning route and amber cells form the route along the top. On the right, e= is the effort when the cell pops and # is the pop order. The red cell is the 8. It sits in the heap at effort 6 but the target pops first, so it is never used.
0.0.There are n cities and a list of flights[i] = (from, to, price). Return the cheapest price from src to dst using at most k stops, or -1 if there is no such route.
k stops means at most k + 1 flights. So this is Bellman-Ford with maxEdges = k + 1.dst in time.i, cost[city] is the cheapest price using at most i flights.0→1 for 100, 1→2 for 100 and 0→2 for 500, with k = 0, so one flight only. In place, the first edge sets cost[1] = 100. The second edge then reads that fresh 100 and sets cost[2] = 200. That is two flights inside a one-flight round, and the answer 200 is wrong. Reading from previous, a snapshot of the last round, means previous[1] is still infinity, so only the direct 500 counts. The copy is what makes “round i” mean “at most i edges”.public static class CheapestFlights
{
/// <summary>Cheapest price from src to dst with at most k stops, or -1.</summary>
/// <param name="n">Number of cities, labelled 0 to n - 1.</param>
/// <param name="flights">Directed [start, end, price] triples, price is 0 or more.</param>
/// <param name="src">Departure city.</param>
/// <param name="dst">Arrival city.</param>
/// <param name="k">Most stops allowed between src and dst.</param>
/// <returns>The cheapest price, or -1 if no route fits within k stops.</returns>
/// <example>
/// FindCheapestPrice(3, [[0, 1, 100], [1, 2, 100], [0, 2, 500]], 0, 2, 1) returns 200.
/// </example>
public static int FindCheapestPrice(int n, int[][] flights, int src, int dst, int k)
{
// MaxValue: marks a city no route has reached. Larger than any real price.
const int Unreached = int.MaxValue;
var cost = new int[n]; // n slots, one per city
Array.Fill(cost, Unreached);
cost[src] = 0; // being at src costs nothing
// k stops means k + 1 flights, so k + 1 rounds. One flight per round.
// Invariant: after round i, cost[c] is the cheapest price using at most i flights.
for (int round = 0; round < k + 1; round++)
{
var previous = (int[])cost.Clone(); // snapshot of last round, read-only here
foreach (var f in flights)
{
int start = f[0], end = f[1], price = f[2]; // [0] from, [1] to, [2] price
// Unreached + price would overflow, so skip cities not yet reached.
if (previous[start] == Unreached)
continue;
// Read from previous, write to cost: one new flight per round, no more.
if (previous[start] + price < cost[end])
cost[end] = previous[start] + price;
}
}
// Still unreached means no route within k + 1 flights, so -1 per the problem.
return cost[dst] == Unreached ? -1 : cost[dst];
}
}
flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1, so 2 rounds:
cost = [0, inf, inf].[0, inf, inf]. Edge 0→1 sets cost[1] = 100. Edge 1→2 reads previous[1] = inf, no change. Edge 0→2 sets cost[2] = 500. Now [0, 100, 500].[0, 100, 500]. Edge 1→2 gives 100 + 100 = 200 < 500, so cost[2] = 200.k = 0 only round 1 runs and the answer is 500.Reading the figure. Each row is cost after one round. Amber cells changed in that round. The green 200 is the answer for k = 1. The red row shows the bug from the box above. Without the copy, a single round chains two flights.
src == dst: price 0, from the start state.-1.(city, flights used). Worth naming, but Bellman-Ford is shorter and easier to prove.An n × n grid holds distinct elevations. At time t the water is at level t, and you can move between neighbouring cells only if both are at most t. Moving takes no time. Starting at the top-left, return the earliest time you can reach the bottom-right.
t exactly when its highest cell is at most t. So the answer is the route that minimises its highest cell.max.visited grid gives lazy deletion with no distance table. A bool[n, n] is faster than a HashSet of tuples.public static class SwimInWater
{
// Four moves: down, up, right, left. Each is a (row change, col change).
private static readonly (int Dr, int Dc)[] Moves = [(1, 0), (-1, 0), (0, 1), (0, -1)];
/// <summary>Earliest time to swim from the top-left to the bottom-right cell.</summary>
/// <param name="grid">An n by n grid of distinct elevations, n at least 1.</param>
/// <returns>The smallest water level that connects the two corners.</returns>
/// <example>
/// EarliestTime([[0, 2], [1, 3]]) returns 3.
/// </example>
public static int EarliestTime(int[][] grid)
{
int n = grid.Length;
var visited = new bool[n, n]; // a bool grid beats a HashSet of tuples here
// Element is the cell, priority is the water level the route needs.
var heap = new PriorityQueue<(int R, int C), int>();
// The start needs water at least as high as its own cell.
heap.Enqueue((0, 0), grid[0][0]);
// Invariant: a cell's first pop carries the lowest level that reaches it.
while (heap.TryDequeue(out var cell, out int level))
{
var (r, c) = cell;
if (visited[r, c]) // stale: settled by an earlier pop
continue;
visited[r, c] = true;
if (r == n - 1 && c == n - 1) // n - 1: the last row and column. Final on pop.
return level;
foreach (var (dr, dc) in Moves)
{
int nr = r + dr, nc = c + dc;
// 0 is the first row or column. n is one past the last.
if (nr < 0 || nr >= n || nc < 0 || nc >= n || visited[nr, nc])
continue;
// The route now needs water up to its highest cell so far.
heap.Enqueue((nr, nc), Math.Max(level, grid[nr][nc]));
}
}
return -1; // -1: not reached, the grid is connected
}
}
grid = [[0, 2], [1, 3]]:
(0, 0, 0). Push down (1, 1, 0) and right (2, 0, 1).(1, 1, 0). Push (3, 1, 1), since the target cell is 3.(2, 0, 1). Its neighbour (1,1) would also give 3. Push it again.(3, 1, 1). Target. Return 3. The second copy is never used.Reading the figure. Each heap entry is (level, row, col). The amber cell has just popped. Green cells are settled, blue cells wait in the heap, and grey cells are not yet reached. Notice the target is pushed twice at level 3. The first pop wins and the copy is never read.
n = 1: answer is grid[0][0], returned on the first pop.Math.Max(grid[0][0], grid[n-1][n-1]). Both corners must be under water.0..n²-1, so binary search on t with a BFS check is a fine alternative, at O(n² log n) too.if (d > dist[node]) continue;.LinkedList<int>. Free edges to the front, paid edges to the back. No log factor.Dijkstra keeps the best candidate at the front of a heap. Pattern 22, the Monotonic Deque, keeps the best candidate at the front of a deque instead, for when the candidates live in a sliding window and expire in order.