Навигация в града с BFS и Dijkstra в C#

Проблем

Куриерът пита за маршрут

Куриерската фирма от модула „Графи“ има склад в града. Картата е текстов файл, по една улица на ред: откъде, накъде и колко минути се кара по нея. - е двупосочна улица, -> е еднопосочна:

Склад - Гара 4
Склад - Пазар 3
Гара - Площад 3
Пазар - Площад 2
Пазар -> Парк 4
Площад - Кино 5
Кино - Болница 3
Парк - Стадион 2
Стадион - Болница 2
Склад - Стадион 16

Диспечерът иска маршрут от Склада до Болницата. Куриерът с велосипед пита за маршрута с най-малко кръстовища, защото на всяко спира. Куриерът с бус пита за най-бързия. Отговорите не са едни и същи.

Този проект е програмата, която чете картата и отговаря и на двата въпроса. Строиш я на стъпки, всяка с изход, с който да сравниш своя.

Идеята

Планът

Картата като граф. Кръстовищата са върхове, улиците са ребра с тегло: минутите. Както в „Граф: списък от съседи и матрица“, пазиш списък от съседи: речник от кръстовище към списък от улици.
Най-малко улици. BFS от Склада на слоеве: първо кръстовищата на една улица, после на две.
Минутите по маршрута. Сбор от минутите на улиците, за да сравниш двата отговора.
Най-бързо. Dijkstra с приоритетна опашка: винаги вади кръстовището с най-малко минути досега.
Обратно. Същата програма от Болницата към Склада. Еднопосочната улица прави пътя обратно различен.

Програмата чете картата от стандартния вход, за да работи с всяка карта. Пускаш я с файла: dotnet run < map.txt.

Упражнение

Стъпка 1: картата

Прочети картата в речник от кръстовище към списък от улици (до кое кръстовище и колко минути). Двупосочната улица влиза в списъците и на двата края, еднопосочната само в списъка на началото. Кръстовище без изходящи улици също трябва да е в речника, с празен списък.

Отпечатай броя кръстовища и съседите на Склада, Пазара и Парка, в реда на редовете от файла:

кръстовища: 8
Склад: Гара 4, Пазар 3, Стадион 16
Пазар: Склад 3, Площад 2, Парк 4
Парк: Стадион 2

Решение

record Street(string To, int Minutes);

static void AddStreet(Dictionary<string, List<Street>> city,
    string a, string b, int minutes, bool twoWay)
{
    if (!city.ContainsKey(a)) city[a] = [];
    if (!city.ContainsKey(b)) city[b] = [];
    city[a].Add(new Street(b, minutes));
    if (twoWay) city[b].Add(new Street(a, minutes));
}

static Dictionary<string, List<Street>> ReadMap(string text)
{
    var city = new Dictionary<string, List<Street>>();
    foreach (var line in text.Trim().Split('\n'))
    {
        var p = line.Split(' ', StringSplitOptions.RemoveEmptyEntries | StringSplitOptions.TrimEntries);
        AddStreet(city, p[0], p[2], int.Parse(p[3]), p[1] == "-");
    }
    return city;
}

static string Neighbors(Dictionary<string, List<Street>> city, string place) =>
    $"{place}: {string.Join(", ", city[place].Select(s => $"{s.To} {s.Minutes}"))}";

var city = ReadMap(Console.In.ReadToEnd());
Console.WriteLine($"кръстовища: {city.Count}");
Console.WriteLine(Neighbors(city, "Склад"));
Console.WriteLine(Neighbors(city, "Пазар"));
Console.WriteLine(Neighbors(city, "Парк"));

record Street стои над class Program. Console.In.ReadToEnd() чете целия вход наведнъж.

Парк има един съсед, Стадиона: Пазар -> Парк е еднопосочна и Пазарът не е в списъка на Парка.

Упражнение

Стъпка 2: най-малко улици

Напиши fewestStreets(city, start, end): BFS от start, който спира, щом извади end, и връща маршрута като списък от кръстовища. За да построиш маршрута, пази за всяко кръстовище откъде си дошъл (prev), а после върви назад от end и обърни списъка.

най-малко улици: Склад → Стадион → Болница

Решение

static List<string> Route(Dictionary<string, string> prev, string end)
{
    var places = new List<string>();
    for (string? at = end; at != null; at = prev.GetValueOrDefault(at)) places.Add(at);
    places.Reverse();
    return places;
}

static List<string> FewestStreets(
    Dictionary<string, List<Street>> city,
    string start, string end)
{
    var prev = new Dictionary<string, string>();
    var seen = new HashSet<string> { start };
    var queue = new Queue<string>([start]);
    while (queue.TryDequeue(out var at))
    {
        if (at == end) return Route(prev, end);
        foreach (var s in city[at])
        {
            if (seen.Add(s.To))
            {
                prev[s.To] = at;
                queue.Enqueue(s.To);
            }
        }
    }
    return [];
}

var city = ReadMap(Console.In.ReadToEnd());
Console.WriteLine($"най-малко улици: {string.Join(" → ", FewestStreets(city, "Склад", "Болница"))}");

Кръстовището се маркира като видяно, когато влиза в опашката, не когато излиза: иначе едно кръстовище влиза няколко пъти.

Упражнение

Стъпка 3: колко минути

Добави minutesOf(city, route), който събира минутите на улиците по маршрута, и describe(city, route), който връща маршрута, броя улици и минутите. Отпечатай маршрута от стъпка 2 с describe:

най-малко улици: Склад → Стадион → Болница (2 улици, 18 мин)

Решение

static int MinutesOf(Dictionary<string, List<Street>> city, List<string> route)
{
    int total = 0;
    for (int i = 1; i < route.Count; i++)
    {
        total += city[route[i - 1]].First(s => s.To == route[i]).Minutes;
    }
    return total;
}

static string Describe(Dictionary<string, List<Street>> city, List<string> route) =>
    $"{string.Join(" → ", route)} ({route.Count - 1} улици, {MinutesOf(city, route)} мин)";

var city = ReadMap(Console.In.ReadToEnd());
Console.WriteLine($"най-малко улици: {Describe(city, FewestStreets(city, "Склад", "Болница"))}");

Две улици, но 18 минути: шестнайсет от тях са по околовръстното.

Виж го

Два маршрута на една карта

static List<string> Fastest(
    Dictionary<string, List<Street>> city,
    string start, string end)
{
    var dist = new Dictionary<string, int> { [start] = 0 };
    var prev = new Dictionary<string, string>();
    var queue = new PriorityQueue<string, int>();
    queue.Enqueue(start, 0);
    while (queue.TryDequeue(out var at, out int minutes))
    {
        if (minutes > dist[at]) continue;
        if (at == end) return Route(prev, end);
        foreach (var s in city[at])
        {
            int t = minutes + s.Minutes;
            if (!dist.TryGetValue(s.To, out int d) || t < d)
            {
                dist[s.To] = t;
                prev[s.To] = at;
                queue.Enqueue(s.To, t);
            }
        }
    }
    return [];
}

static List<string> FewestStreets(
    Dictionary<string, List<Street>> city,
    string start, string end)
{
    var prev = new Dictionary<string, string>();
    var seen = new HashSet<string> { start };
    var queue = new Queue<string>([start]);
    while (queue.TryDequeue(out var at))
    {
        if (at == end) return Route(prev, end);
        foreach (var s in city[at])
        {
            if (seen.Add(s.To))
            {
                prev[s.To] = at;
                queue.Enqueue(s.To);
            }
        }
    }
    return [];
}

Стъпка по стъпка, с думи

Картата: 8 кръстовища и 10 улици с минутите им. Пазар → Парк е еднопосочна, околовръстното от Склад до Стадион е 16 мин.
BFS, на една улица от Склад: Гара, Пазар, Стадион. Минутите не го интересуват.
На две улици: Площад, Парк, Болница. Болница вече е в опашката, от Стадион.
Най-малко улици: Склад → Стадион → Болница, 2 улици, но 18 мин: 16 от тях са по околовръстното.
Dijkstra: опашката е подредена по минути. Склад 0, съседите му влизат в опашката: Гара 4, Пазар 3, Стадион 16.
Най-бързото в опашката е Пазар, 3 мин. Ново: Площад 5, Парк 7.
Гара, 4 мин: през него нищо не става по-бързо.
Най-бързото в опашката е Площад, 5 мин. Ново: Кино 10.
Парк с 7 мин. През него Стадион пада от 16 на 9.
Най-бързото в опашката е Стадион, 9 мин. Ново: Болница 11.
Кино, 10 мин: през него нищо не става по-бързо.
Болница излиза с 11 мин: нищо в опашката не е по-бързо, значи това е отговорът.
Най-бързо: Склад → Пазар → Парк → Стадион → Болница, 4 улици, 11 мин.
Два отговора на два въпроса: 2 улици и 18 мин или 4 улици и 11 мин. За куриера важат минутите.

BFS вижда само броя улици и избира околовръстното. Dijkstra вади кръстовищата по минути и стига до Болницата за 11 мин през Пазара, еднопосочната улица и Стадиона. Стадионът първо е с 16 мин по шосето, после пада на 9 през Парка.

Упражнение

Стъпка 4: най-бързо

Напиши fastest(city, start, end) с Dijkstra: dist пази най-малките минути досега, опашката е подредена по минути, а prev пази маршрута. Отпечатай и двата маршрута:

най-малко улици: Склад → Стадион → Болница (2 улици, 18 мин)
най-бързо: Склад → Пазар → Парк → Стадион → Болница (4 улици, 11 мин)

Решение

static List<string> Fastest(
    Dictionary<string, List<Street>> city,
    string start, string end)
{
    var dist = new Dictionary<string, int> { [start] = 0 };
    var prev = new Dictionary<string, string>();
    var queue = new PriorityQueue<string, int>();
    queue.Enqueue(start, 0);
    while (queue.TryDequeue(out var at, out int minutes))
    {
        if (minutes > dist[at]) continue;
        if (at == end) return Route(prev, end);
        foreach (var s in city[at])
        {
            int t = minutes + s.Minutes;
            if (!dist.TryGetValue(s.To, out int d) || t < d)
            {
                dist[s.To] = t;
                prev[s.To] = at;
                queue.Enqueue(s.To, t);
            }
        }
    }
    return [];
}

var city = ReadMap(Console.In.ReadToEnd());
Console.WriteLine($"най-малко улици: {Describe(city, FewestStreets(city, "Склад", "Болница"))}");
Console.WriteLine($"най-бързо: {Describe(city, Fastest(city, "Склад", "Болница"))}");

PriorityQueue<string, int> пази кръстовището с приоритет минутите. TryDequeue(out var at, out int minutes) дава и двете. TryGetValue казва дали кръстовището вече има минути.

Пробвай

Попълни

Кръстовище може да влезе в опашката няколко пъти, когато минутите до него паднат. Старият запис остава. Какво прави програмата, когато го извади?

if (minutes > dist[at]) ;

Пробвай

Предвиди пътя обратно

Куриерът се връща от Болницата към Склада. Програмата пита fastest(city, "Болница", "Склад"). Какво печата?

var city = ReadMap(Console.In.ReadToEnd());
Console.WriteLine($"обратно: {Describe(city, Fastest(city, "Болница", "Склад"))}");

Отговор

обратно: Болница → Кино → Площад → Пазар → Склад (4 улици, 13 мин)

обратно: Болница → Стадион → Склад (2 улици, 18 мин)

обратно: Болница → Стадион → Парк → Пазар → Склад (4 улици, 11 мин)

Упражнение

Стъпка 5: цялата програма

Добави пътя обратно. Цялата програма печата:

най-малко улици: Склад → Стадион → Болница (2 улици, 18 мин)
най-бързо: Склад → Пазар → Парк → Стадион → Болница (4 улици, 11 мин)
обратно: Болница → Кино → Площад → Пазар → Склад (4 улици, 13 мин)

Цялата програма

record Street(string To, int Minutes);

class Program
{
    static void AddStreet(Dictionary<string, List<Street>> city,
        string a, string b, int minutes, bool twoWay)
    {
        if (!city.ContainsKey(a)) city[a] = [];
        if (!city.ContainsKey(b)) city[b] = [];
        city[a].Add(new Street(b, minutes));
        if (twoWay) city[b].Add(new Street(a, minutes));
    }

    static Dictionary<string, List<Street>> ReadMap(string text)
    {
        var city = new Dictionary<string, List<Street>>();
        foreach (var line in text.Trim().Split('\n'))
        {
            var p = line.Split(' ', StringSplitOptions.RemoveEmptyEntries | StringSplitOptions.TrimEntries);
            AddStreet(city, p[0], p[2], int.Parse(p[3]), p[1] == "-");
        }
        return city;
    }

    static List<string> Route(Dictionary<string, string> prev, string end)
    {
        var places = new List<string>();
        for (string? at = end; at != null; at = prev.GetValueOrDefault(at)) places.Add(at);
        places.Reverse();
        return places;
    }

    static List<string> FewestStreets(
        Dictionary<string, List<Street>> city,
        string start, string end)
    {
        var prev = new Dictionary<string, string>();
        var seen = new HashSet<string> { start };
        var queue = new Queue<string>([start]);
        while (queue.TryDequeue(out var at))
        {
            if (at == end) return Route(prev, end);
            foreach (var s in city[at])
            {
                if (seen.Add(s.To))
                {
                    prev[s.To] = at;
                    queue.Enqueue(s.To);
                }
            }
        }
        return [];
    }

    static int MinutesOf(Dictionary<string, List<Street>> city, List<string> route)
    {
        int total = 0;
        for (int i = 1; i < route.Count; i++)
        {
            total += city[route[i - 1]].First(s => s.To == route[i]).Minutes;
        }
        return total;
    }

    static string Describe(Dictionary<string, List<Street>> city, List<string> route) =>
        $"{string.Join(" → ", route)} ({route.Count - 1} улици, {MinutesOf(city, route)} мин)";

    static List<string> Fastest(
        Dictionary<string, List<Street>> city,
        string start, string end)
    {
        var dist = new Dictionary<string, int> { [start] = 0 };
        var prev = new Dictionary<string, string>();
        var queue = new PriorityQueue<string, int>();
        queue.Enqueue(start, 0);
        while (queue.TryDequeue(out var at, out int minutes))
        {
            if (minutes > dist[at]) continue;
            if (at == end) return Route(prev, end);
            foreach (var s in city[at])
            {
                int t = minutes + s.Minutes;
                if (!dist.TryGetValue(s.To, out int d) || t < d)
                {
                    dist[s.To] = t;
                    prev[s.To] = at;
                    queue.Enqueue(s.To, t);
                }
            }
        }
        return [];
    }

    static void Main()
    {
        var city = ReadMap(Console.In.ReadToEnd());
        Console.WriteLine($"най-малко улици: {Describe(city, FewestStreets(city, "Склад", "Болница"))}");
        Console.WriteLine($"най-бързо: {Describe(city, Fastest(city, "Склад", "Болница"))}");
        Console.WriteLine($"обратно: {Describe(city, Fastest(city, "Болница", "Склад"))}");
    }
}

Пробвай

Намери грешката

Колега е опростил addStreet. Сега пътят обратно излиза 11 мин:

обратно: Болница → Стадион → Парк → Пазар → Склад (4 улици, 11 мин)

Избери реда с грешката.

Виж го

Измери: градът расте

Истинският град има хиляди кръстовища. Решетката е проверка на скоростта: n кръстовища в квадрат, улиците са между съседите, с минути по формула. Куриерът тръгва от горния ляв ъгъл към долния десен:

static Dictionary<string, List<Street>> GridCity(int size)
{
    var city = new Dictionary<string, List<Street>>();
    for (int r = 0; r < size; r++)
    {
        for (int c = 0; c < size; c++)
        {
            string at = $"{r}:{c}";
            if (c + 1 < size) AddStreet(city, at, $"{r}:{c + 1}", 1 + (r * 7 + c * 13) % 9, true);
            if (r + 1 < size) AddStreet(city, at, $"{r + 1}:{c}", 1 + (r * 11 + c * 5) % 9, true);
        }
    }
    return city;
}

var city = GridCity(100);
Console.WriteLine($"кръстовища: {city.Count}");
var few = FewestStreets(city, "0:0", "99:99");
Console.WriteLine($"най-малко улици: {few.Count - 1} улици, {MinutesOf(city, few)} мин");
var fast = Fastest(city, "0:0", "99:99");
Console.WriteLine($"най-бързо: {MinutesOf(city, fast)} мин");

кръстовища: 10000
най-малко улици: 198 улици, 990 мин
най-бързо: 693 мин

Пусни двата алгоритъма в браузъра. BFS гледа всяка улица веднъж: O(n). Dijkstra също, но всеки запис в heap-а струва O(log n): O(n log n). При n = 1000 това са 3966 срещу 15 778 операции, а при n = 100 000 са 398 158 срещу 2 348 779:

BFS: най-малко улици O(n)
Dijkstra: най-бързо O(n log n)

Алгоритъм	n = 10	n = 1000	n = 100 000
BFS: най-малко улици	22	3966	398 158
Dijkstra: най-бързо	34	15 778	2 348 779

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

static List<string> Fastest(
    Dictionary<string, List<Street>> city,
    string start, string end)
{
    var dist = new Dictionary<string, int> { [start] = 0 };
    var prev = new Dictionary<string, string>();
    var queue = new PriorityQueue<string, int>();
    queue.Enqueue(start, 0);
    while (queue.TryDequeue(out var at, out int minutes))
    {
        if (minutes > dist[at]) continue;
        if (at == end) return Route(prev, end);
        foreach (var s in city[at])
        {
            int t = minutes + s.Minutes;
            if (!dist.TryGetValue(s.To, out int d) || t < d)
            {
                dist[s.To] = t;
                prev[s.To] = at;
                queue.Enqueue(s.To, t);
            }
        }
    }
    return [];
}

По-точно, за любопитните

Dijkstra е по-бавен, но отговаря на въпроса за минутите, а BFS не може. И двата спират, щом извадят целта: за близка цел огледат малка част от града.

Навигациите за цели държави не пускат обикновен Dijkstra от всяко място. Те предварително обработват картата (например contraction hierarchies) и търсят с A*, който добавя оценка колко остава до целта. Основата пак е Dijkstra.

Упражнение

Ремонт на улицата

Реши задачата в редактора си.

Затворена улица. Улицата Парк – Стадион е затворена за ремонт. Добави към readMap множество от затворени улици ("Парк Стадион"), което пропуска тези редове в двете посоки. Отпечатай двата маршрута от Склада до Болницата:

най-малко улици: Склад → Стадион → Болница (2 улици, 18 мин)
най-бързо: Склад → Пазар → Площад → Кино → Болница (4 улици, 13 мин)

Още задачи

Само минутите. Напиши вариант на fastest, който връща минутите до всяко кръстовище, без да спира при целта. Кое кръстовище е най-далеч от Склада?
Без кръстовище. Площадът е затворен за събитие. Как ще го пропуснеш, без да пипаш картата?
Свободно шосе. През нощта околовръстното е празно и се кара за 6 мин. Смени минутите в картата: кой е най-бързият маршрут сега и съвпада ли с този на BFS?

Тест

Провери се

1. BFS и Dijkstra дават различни маршрути от Склада до Болницата. Кой е грешният?Dijkstra, защото минава повече улициНито един: BFS отговаря на „най-малко улици“, Dijkstra на „най-малко минути“BFS, защото е по-бавен

2. Защо BFS не намира най-бързия маршрут в този град?Улиците имат различни минути, а BFS брои всяка улица за еднаЗащото опашката е FIFOЗащото има еднопосочна улица

3. В Dijkstra записът, който излиза от опашката, понякога е с повече минути от dist. Какво прави програмата?Прескача го: кръстовището вече е извадено с по-малко минутиОбновява dist с по-голямото числоСпира

Когато минутите до кръстовище паднат, програмата слага нов запис, а старият остава в опашката. Когато старият излезе, той е остарял: minutes > dist[at], и се прескача.

4. Пазар -> Парк е еднопосочна. Какво трябва да има в списъка със съседи?Парк в съседите на Пазара, но не Пазар в съседите на ПаркаИ дветеСамо Пазар в съседите на Парка

5. Градът е решетка с n кръстовища. Как расте броят операции на двата алгоритъма?И двата O(n)И двата O(n²)BFS O(n), Dijkstra O(n log n): heap-ът добавя log n на улица

Навигация в града

Бисквитки