Dijkstra

// Edsger Dijkstra thought this up in 1956, in his head, in twenty minutes, over a
// cup of coffee. It answers a question that sounds harmless and is not: what is the
// cheapest way from here to there, when every step may cost something different?
//
// The idea is to be stubbornly cautious. Of everything that has been reached so far,
// always carry on with the cheapest place. Whatever is taken off the queue that way
// can never be reached more cheaply later on, because every other way starts out
// more expensive already - and costs never go down.
public static class Dijkstra
{
    public static Route Search(IGraph graph, int start, int goal)
    {
        // The cheapest price known so far for every place that has been reached.
        var cheapest = new Dictionary<int, double> { [start] = 0 };

        // Where each place was reached from. This is what the path is built from.
        var cameFrom = new Dictionary<int, int>();

        // Places that have been reached but not looked at yet, cheapest one first.
        var queue = new PriorityQueue<int, double>();

        // Places that are settled: their price cannot get any better. They are also
        // kept in the order they were settled, which is what the pictures show.
        var settled = new HashSet<int>();
        var seen = new List<int>();

        queue.Enqueue(start, 0);

        while (queue.TryDequeue(out var node, out var cost))
        {
            // The queue may still hold older, more expensive entries for this place.
            if (!settled.Add(node))
                continue;

            seen.Add(node);

            if (node == goal)
                return Route.Backwards(cameFrom, start, goal, cost, [.. seen]);

            foreach (var step in graph.Neighbours(node))
            {
                var price = cost + step.Cost;

                // Only worth remembering when this way is cheaper than the known one.
                if (cheapest.TryGetValue(step.Node, out var known) && known <= price)
                    continue;

                cheapest[step.Node] = price;
                cameFrom[step.Node] = node;

                queue.Enqueue(step.Node, price);
            }
        }

        return Route.Nothing([.. seen]);
    }
}

// One step away from a node: where it leads and what it costs to go there.
public readonly record struct Step(int Node, double Cost);

// Both searches ask a map only ever one question, so this is all a map has to
// answer: which nodes can be reached from here, and what does each of them cost?
public interface IGraph
{
    IEnumerable<Step> Neighbours(int node);
}

// What a search came back with: the way from start to goal, what that way costs,
// and every node it had to take off the queue on the way there, in that order.
// The last one is what makes the difference between the two searches visible.
public sealed record Route(int[] Path, double Cost, int[] Seen)
{
    public bool Found => Path.Length > 0;

    public int Visited => Seen.Length;

    public static Route Nothing(int[] seen) => new([], double.PositiveInfinity, seen);

    // Every node remembers where it was reached from. Walking that chain backwards
    // from the goal and turning it around gives the way there.
    public static Route Backwards(Dictionary<int, int> cameFrom, int start, int goal, double cost, int[] seen)
    {
        var path = new List<int> { goal };

        while (path[^1] != start)
            path.Add(cameFrom[path[^1]]);

        path.Reverse();

        return new Route([.. path], cost, seen);
    }
}

string[] places =
[
    "Köln", "Düsseldorf", "Dortmund", "Kassel", "Frankfurt", "Mannheim",
    "Karlsruhe", "Stuttgart", "Würzburg", "Nürnberg", "München", "Erfurt",
    "Leipzig", "Berlin", "Hannover",
];

var roads = new RoadMap(places.Length);

// Every road with its length in kilometres, roughly as it really is.
roads.Connect(0, 1, 40);    // Köln - Düsseldorf
roads.Connect(0, 2, 95);    // Köln - Dortmund
roads.Connect(0, 4, 190);   // Köln - Frankfurt
roads.Connect(1, 2, 70);    // Düsseldorf - Dortmund
roads.Connect(2, 3, 165);   // Dortmund - Kassel
roads.Connect(3, 4, 190);   // Kassel - Frankfurt
roads.Connect(3, 11, 155);  // Kassel - Erfurt
roads.Connect(4, 5, 85);    // Frankfurt - Mannheim
roads.Connect(4, 8, 120);   // Frankfurt - Würzburg
roads.Connect(5, 6, 80);    // Mannheim - Karlsruhe
roads.Connect(6, 7, 80);    // Karlsruhe - Stuttgart
roads.Connect(7, 8, 155);   // Stuttgart - Würzburg
roads.Connect(7, 10, 220);  // Stuttgart - München
roads.Connect(8, 9, 110);   // Würzburg - Nürnberg
roads.Connect(9, 10, 170);  // Nürnberg - München
roads.Connect(9, 11, 225);  // Nürnberg - Erfurt
roads.Connect(11, 12, 130); // Erfurt - Leipzig
roads.Connect(12, 13, 190); // Leipzig - Berlin
roads.Connect(2, 14, 210);  // Dortmund - Hannover
roads.Connect(3, 14, 165);  // Kassel - Hannover
roads.Connect(13, 14, 285); // Berlin - Hannover

var route = Dijkstra.Search(roads, start: 0, goal: 10);

Console.WriteLine($"from {places[route.Path[0]]} to {places[route.Path[^1]]}: {route.Cost} km");
Console.WriteLine(string.Join(" - ", route.Path.Select(place => places[place])));
Console.WriteLine($"{route.Visited} of {places.Length} places had to be looked at");

// The same map, a different goal. Dijkstra settles the places in the order
// of their distance from the start, so on the way to Berlin it has already
// worked out the cheapest way to every place that lies closer.
var north = Dijkstra.Search(roads, start: 0, goal: 13);

Console.WriteLine();
Console.WriteLine($"from {places[0]} to {places[13]}: {north.Cost} km");
Console.WriteLine(string.Join(" - ", north.Path.Select(place => places[place])));