C#: uniform-cost search with PriorityQueue
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.
C#
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);
}
}
}