C#: uniform-cost search with PriorityQueue

Before you start

C# dictionaries, tuples, and generic collections.

Find the cheapest route from a start node to every other node in a weighted graph.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

Uniform-cost search, which is Dijkstra's algorithm, expands the node with the smallest known path cost first. It keeps a priority queue of (node, cost) entries and a table of the best cost found for each node. When a cheaper route to a node is found, the table and queue are updated.

Because the queue always yields the cheapest unexpanded entry, the first time a node is taken from it, its cost is final, provided all edge costs are non-negative. Entries that are older than the table value are stale and are skipped. The graph below is the standard textbook example with six nodes.

Code example

using System;
using System.Collections.Generic;
using System.Linq;

class Program {
  static void Main() {
    var graph = new Dictionary<string, List<(string To, int Cost)>>();
    void Edge(string a, string b, int cost) {
      if (!graph.ContainsKey(a)) graph[a] = new List<(string, int)>();
      if (!graph.ContainsKey(b)) graph[b] = new List<(string, int)>();
      graph[a].Add((b, cost));
      graph[b].Add((a, cost));
    }
    Edge("A", "B", 7); Edge("A", "C", 9); Edge("A", "F", 14);
    Edge("B", "C", 10); Edge("B", "D", 15); Edge("C", "D", 11);
    Edge("C", "F", 2); Edge("D", "E", 6); Edge("E", "F", 9);

    var best = graph.Keys.ToDictionary(k => k, k => int.MaxValue);
    var queue = new PriorityQueue<string, int>();
    best["A"] = 0;
    queue.Enqueue("A", 0);
    while (queue.TryDequeue(out string node, out int cost)) {
      if (cost > best[node]) {
        continue;
      }
      foreach (var (to, step) in graph[node]) {
        if (cost + step < best[to]) {
          best[to] = cost + step;
          queue.Enqueue(to, best[to]);
        }
      }
    }
    foreach (var pair in best.OrderBy(p => p.Key)) {
      Console.WriteLine(pair.Key + ": " + pair.Value);
    }
  }
}

Output

A: 0
B: 7
C: 9
D: 20
E: 20
F: 11

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1using System;

2using System.Collections.Generic;

3using System.Linq;

5class Program {

6 static void Main() {

7 var graph = new Dictionary<string, List<(string To, int Cost)>>();

8 void Edge(string a, string b, int cost) {

9 if (!graph.ContainsKey(a)) graph[a] = new List<(string, int)>();

10 if (!graph.ContainsKey(b)) graph[b] = new List<(string, int)>();

11 graph[a].Add((b, cost));

12 graph[b].Add((a, cost));

13 }

14 Edge("A", "B", 7); Edge("A", "C", 9); Edge("A", "F", 14);

15 Edge("B", "C", 10); Edge("B", "D", 15); Edge("C", "D", 11);

16 Edge("C", "F", 2); Edge("D", "E", 6); Edge("E", "F", 9);

18 var best = graph.Keys.ToDictionary(k => k, k => int.MaxValue);

19 var queue = new PriorityQueue<string, int>();

20 best["A"] = 0;

21 queue.Enqueue("A", 0);

22 while (queue.TryDequeue(out string node, out int cost)) {

23 if (cost > best[node]) {

24 continue;

25 }

26 foreach (var (to, step) in graph[node]) {

27 if (cost + step < best[to]) {

28 best[to] = cost + step;

29 queue.Enqueue(to, best[to]);

30 }

31 }

32 }

33 foreach (var pair in best.OrderBy(p => p.Key)) {

34 Console.WriteLine(pair.Key + ": " + pair.Value);

35 }

36 }

37}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
The start has cost 0; every other node is initially unreachable.	`best = A:0, others ∞`	—
Always take the unexpanded entry with the smallest cost.	`best = A:0, others ∞`	—
A cheaper route was found after this entry was queued, so skip the stale entry.	`best = A:0, others ∞`	—
A cheaper route to a neighbour is recorded and queued. For example C is reached at cost 9, then F improves from 14 to 11 via C.	`F: 14 → 11`	—
Final cheapest costs from A.	`F: 14 → 11`	A: 0 B: 7 C: 9 D: 20 E: 20 F: 11

Behind the scenes

How C# processes this code

C# compiles to code for the .NET runtime, which invokes the program entry point.

Cost and common mistakes

O((V + E) log V) time with a binary-heap priority queue.

Dijkstra's algorithm gives wrong answers when any edge cost is negative. Use Bellman–Ford instead.
PriorityQueue has no decrease-key operation, so a node can be queued several times. The stale-entry check handles it.
Without a heuristic it explores in all directions. A* adds an estimate of the remaining cost to focus the search.

Try it yourself

What is the cost of the cheapest route from A to D?

Reveal answer and reasoning

20, by A → C → D (9 + 11), which beats A → B → D (7 + 15 = 22).