Dijkstra

// Edsger Dijkstra hat sich das 1956 ausgedacht, im Kopf, in zwanzig Minuten, bei einer
// Tasse Kaffee. Es beantwortet eine Frage, die harmlos klingt und es nicht ist: Was ist
// der günstigste Weg von hier nach dort, wenn jeder Schritt etwas anderes kosten kann?
//
// Die Idee ist sture Vorsicht. Von allem, was bisher erreicht wurde, immer mit dem
// billigsten Ort weitermachen. Was auf diese Weise aus der Warteschlange kommt, kann
// später nie mehr billiger erreicht werden, denn jeder andere Weg beginnt schon
// teurer - und Kosten werden nie kleiner.
public static class Dijkstra
{
    public static Route Search(IGraph graph, int start, int goal)
    {
        // Der billigste bisher bekannte Preis für jeden erreichten Ort.
        var cheapest = new Dictionary<int, double> { [start] = 0 };

        // Woher jeder Ort erreicht wurde. Daraus wird am Ende der Weg gebaut.
        var cameFrom = new Dictionary<int, int>();

        // Orte, die erreicht, aber noch nicht angeschaut wurden, der billigste zuerst.
        var queue = new PriorityQueue<int, double>();

        // Abgehakte Orte: Ihr Preis kann nicht mehr besser werden. Sie werden außerdem in
        // der Reihenfolge festgehalten, in der sie abgehakt wurden - das zeigen die Bilder.
        var settled = new HashSet<int>();
        var seen = new List<int>();

        queue.Enqueue(start, 0);

        while (queue.TryDequeue(out var node, out var cost))
        {
            // Die Warteschlange kann noch ältere, teurere Einträge für diesen Ort enthalten.
            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;

                // Nur zu merken, wenn dieser Weg billiger ist als der bekannte.
                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]);
    }
}

// Ein Schritt von einem Knoten weg: wohin er führt und was er kostet.
public readonly record struct Step(int Node, double Cost);

// Beide Suchen stellen einer Karte immer nur eine Frage, und mehr muss eine Karte
// nicht beantworten: Welche Knoten sind von hier erreichbar, und was kostet jeder?
public interface IGraph
{
    IEnumerable<Step> Neighbours(int node);
}

// Was eine Suche zurückbringt: den Weg von Start zu Ziel, seine Kosten und jeden
// Knoten, den sie dafür aus der Warteschlange nehmen musste, in dieser Reihenfolge.
// Das Letzte macht den Unterschied zwischen den beiden Suchen sichtbar.
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);

    // Jeder Knoten merkt sich, woher er erreicht wurde. Läuft man diese Kette vom Ziel
    // aus rückwärts und dreht sie um, ergibt das den Weg.
    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);

// Jede Straße mit ihrer Länge in Kilometern, ungefähr so, wie sie wirklich ist.
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");

// Dieselbe Karte, ein anderes Ziel. Dijkstra hakt die Orte in der Reihenfolge ihrer
// Entfernung vom Start ab, auf dem Weg nach Berlin hat er also den günstigsten Weg zu
// jedem näher gelegenen Ort schon ausgerechnet.
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])));