C#: uniform-cost search with PriorityQueue

Find the cheapest route from a start node to every other node in a weighted graph.

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

Explanation

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.

Explore the dry run

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

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).

C#: uniform-cost search with PriorityQueue

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading