How it works
Dijkstra's algorithm finds shortest path costs when edge weights are nonnegative. A priority queue selects the smallest currently proposed distance. The sample reaches C for cost one, improves B from four to three through C, and then reaches D for total cost four through B.
The implementation enqueues a new proposal whenever a shorter distance is found. It does not remove the older proposal already stored in the queue. That older entry is harmless only because the dequeue loop compares its cost with the current distance and skips entries that have been superseded.
Negative edge costs violate this algorithm's assumptions, so the sample rejects them before processing. It also uses checked addition to avoid silently wrapping an overflowing path cost into a misleading small number. A larger application may choose a wider distance type and a separate representation for unreachable nodes.
The final report explicitly orders node names. PriorityQueue does not promise a useful stable order among equal priorities, and shortest-distance correctness should not depend on such a tie. Different valid exploration orders can produce the same distance map, which is the actual result this exercise verifies.
Practice by increasing the A-to-B edge cost, removing the C-to-B edge, and adding a declared unreachable node. Predict which distances change and how unreachable state should be displayed instead of printing the int.MaxValue sentinel as a meaningful cost.
Finally, add predecessor tracking whenever a distance improves, then reconstruct one shortest route to D. Keep route reporting separate from distance calculation and define a tie policy if several routes share the same minimum cost. Tests should include stale proposals, disconnected nodes, zero-cost edges, and rejected negative costs rather than only a single straight chain.
A working example
using System;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;
using System.Text;
using System.Text.Json;
using System.Text.Json.Serialization;
using System.Threading;
using System.Threading.Tasks;
using System.Runtime.CompilerServices;
var graph = new Dictionary<string, (string To, int Cost)[]> {
["A"] = new[] { ("B", 4), ("C", 1) }, ["B"] = new[] { ("D", 1) },
["C"] = new[] { ("B", 2), ("D", 5) }, ["D"] = Array.Empty<(string, int)>()
};
if (graph.Values.SelectMany(edges => edges).Any(edge => edge.Cost < 0)) throw new ArgumentException("Negative edge");
var distance = graph.Keys.ToDictionary(key => key, _ => int.MaxValue, StringComparer.Ordinal);
var queue = new PriorityQueue<string, int>();
distance["A"] = 0; queue.Enqueue("A", 0);
while (queue.TryDequeue(out string? node, out int cost)) {
if (cost != distance[node]) continue;
foreach (var edge in graph[node]) {
int candidate = checked(cost + edge.Cost);
if (candidate < distance[edge.To]) {
distance[edge.To] = candidate; queue.Enqueue(edge.To, candidate);
}
}
}
Console.WriteLine(string.Join(",", distance.OrderBy(pair => pair.Key, StringComparer.Ordinal).Select(pair => $"{pair.Key}:{pair.Value}")));
Expected output
A:0,B:3,C:1,D:4
A later improvement can leave an older queue entry behind; compare it with the current best distance.