Към съдържанието
wannacode

Dijkstra

Накратко: Алгоритъмът на Dijkstra намира най-кратките пътища от един връх в граф с неотрицателни тегла, като взима най-близкия връх от приоритетна опашка: O((V + E) log V).

Проблем

Най-малко улици не е най-бързо

Куриерът тръгва от склада към клиент. Приложението трябва да му даде най-бързия маршрут. Всяка улица има време в минути: булевардът е широк, но в задръстване, а малките улички са бързи.

Градът е граф, улиците са ребрата му в двете посоки (виж представянето на граф):

static void AddStreet(Dictionary<string, List<Street>> city,
    string a, string b, int minutes)
{
    if (!city.ContainsKey(a)) city[a] = [];
    if (!city.ContainsKey(b)) city[b] = [];
    city[a].Add(new Street(b, minutes));
    city[b].Add(new Street(a, minutes));
}
var city = new Dictionary<string, List<Street>>();
AddStreet(city, "Склад", "Мост", 2);
AddStreet(city, "Склад", "Площад", 5);
AddStreet(city, "Склад", "Пазар", 15);
AddStreet(city, "Мост", "Площад", 1);
AddStreet(city, "Мост", "Гара", 8);
AddStreet(city, "Площад", "Гара", 3);
AddStreet(city, "Площад", "Пазар", 9);
AddStreet(city, "Гара", "Клиент", 3);
AddStreet(city, "Пазар", "Клиент", 2);

Първата идея е BFS от предишния урок: той намира най-късия път. Но BFS брои улиците, не минутите:

static Dictionary<string, string> FewestStreets(
    Dictionary<string, List<Street>> city, string start)
{
    var prev = new Dictionary<string, string>();
    var seen = new HashSet<string> { start };
    var queue = new Queue<string>([start]);
    while (queue.TryDequeue(out var place))
    {
        foreach (Street street in city[place])
        {
            if (seen.Add(street.To))
            {
                prev[street.To] = place;
                queue.Enqueue(street.To);
            }
        }
    }
    return prev;
}
var city = new Dictionary<string, List<Street>>();
AddStreet(city, "Склад", "Мост", 2);
AddStreet(city, "Склад", "Площад", 5);
AddStreet(city, "Склад", "Пазар", 15);
AddStreet(city, "Мост", "Площад", 1);
AddStreet(city, "Мост", "Гара", 8);
AddStreet(city, "Площад", "Гара", 3);
AddStreet(city, "Площад", "Пазар", 9);
AddStreet(city, "Гара", "Клиент", 3);
AddStreet(city, "Пазар", "Клиент", 2);
var r = Route(FewestStreets(city, "Склад"), "Клиент");
Console.WriteLine($"Най-малко улици: {string.Join(" → ", r)} ({r.Count - 1} улици, {Minutes(city, r)} мин)");
Изход
Най-малко улици: Склад → Пазар → Клиент (2 улици, 17 мин)

Две улици, но 17 минути: 15 по булеварда до пазара и 2 до клиента. През моста, площада и гарата са четири улици и само 9 минути. BFS дори не гледа минутите.

Идеята

Най-близкото място първо

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

Това прави алгоритъмът на Dijkstra (Едсхер Дейкстра, 1956). Пази за всяко място най-доброто време досега, dist, и опашка от записи „минути, място“.

  1. Отначало dist е 0 за склада, а всяко друго място е недостигнато (∞).
  2. Вземи от опашката записа с най-малко минути. Това е приоритетна опашка: вади най-малкото за O(log n).
  3. За всяка улица от това място пробвай: стига ли се по нея до съседа по-бързо от досегашното? Ако да, запиши новото време, запомни откъде си дошъл (prev) и сложи нов запис в опашката. Това пробване се казва релаксация (relaxation).
  4. Повтаряй, докато опашката свърши.

Защо мястото, което излиза от опашката, вече има окончателното си време? Всички други записи са с поне толкова минути, а всяка улица добавя минути. Никой път през тях не може да стигне по-рано.

Виж го

Dijkstra отвътре

static Paths Dijkstra(
    Dictionary<string, List<Street>> city, string start)
{
    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 place, out var minutes))
    {
        if (minutes > dist[place]) continue; // остаряло
        foreach (Street street in city[place])
        {
            int t = minutes + street.Minutes;
            if (!dist.TryGetValue(street.To, out int old)
                || t < old)
            {
                dist[street.To] = t;
                prev[street.To] = place;
                queue.Enqueue(street.To, t);
            }
        }
    }
    return new Paths(dist, prev);
}
PriorityQueue<string, int> пази мястото, а приоритетът е минутите. TryDequeue дава и двете. Ако TryGetValue не намери мястото, то още не е достигнато: това е ∞.

prev пази маршрута отзад напред: за всяко място, откъде е дошъл най-бързият път. Тръгваш от клиента, следваш prev до склада и обръщаш:

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;
}
var paths = Dijkstra(city, "Склад");
var r = Route(paths.Prev, "Клиент");
Console.WriteLine($"Най-бързо: {string.Join(" → ", r)} ({r.Count - 1} улици, {Minutes(city, r)} мин)");
Изход
Най-бързо: Склад → Мост → Площад → Гара → Клиент (4 улици, 9 мин)

static Paths Dijkstra(
    Dictionary<string, List<Street>> city, string start)
{
    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 place, out var minutes))
    {
        if (minutes > dist[place]) continue; // остаряло
        foreach (Street street in city[place])
        {
            int t = minutes + street.Minutes;
            if (!dist.TryGetValue(street.To, out int old)
                || t < old)
            {
                dist[street.To] = t;
                prev[street.To] = place;
                queue.Enqueue(street.To, t);
            }
        }
    }
    return new Paths(dist, prev);
}
Стъпка по стъпка, с думи
  1. Куриерът тръгва от Склад: 0 минути. Всяко друго място е ∞, още нищо не го е стигнало. В опашката има един запис: 0 Склад.
  2. Взима се най-малкият запис, 0 Склад. Всяка улица от него дава време: Мост 2, Площад 5, Пазар 15. Всички са по-добри от ∞: записват се и влизат в опашката.
  3. Следва 2 Мост. През него Площад е 2 + 1 = 3, по-добро от 5: времето и prev се сменят, влиза 3 Площад. Старото 5 Площад остава в опашката, вече е остаряло. Гара получава 10.
  4. 3 Площад: окончателно, нищо в опашката не може да го направи по-бързо. През него Гара пада от 10 на 6, а Пазар от 15 на 12.
  5. Отгоре е 5 Площад, но Площад вече има 3. Записът е остарял: прескача се. Това е мързеливото изтриване: вместо да търсиш стария запис в опашката, го изхвърляш, когато излезе.
  6. 6 Гара: окончателно. Клиент получава 6 + 3 = 9. Обратно към Мост с 14 и Площад с 9 не е по-добре.
  7. 9 Клиент: окончателно, 9 минути. През Клиент Пазар пада от 12 на 11. Границата расте по време, а не по брой улици.
  8. Останалото: 10 Гара е остаряло, 11 Пазар е окончателно и не подобрява нищо, 12 и 15 Пазар са остарели. Опашката е празна.
  9. prev дава маршрута отзад напред: Клиент ← Гара ← Площад ← Мост ← Склад. Обърнат: Склад → Мост → Площад → Гара → Клиент, 9 минути, четири улици. Маршрутът с две улици през Пазар е 17.

Местата стават окончателни по реда на времето си: Склад 0, Мост 2, Площад 3, Гара 6, Клиент 9, Пазар 11. Пазарът, който е на една улица от склада, е последен.

Пробвай

Предвиди изхода

Колко минути до пазара дава Dijkstra?

var city = new Dictionary<string, List<Street>>();
AddStreet(city, "Склад", "Мост", 2);
AddStreet(city, "Склад", "Площад", 5);
AddStreet(city, "Склад", "Пазар", 15);
AddStreet(city, "Мост", "Площад", 1);
AddStreet(city, "Мост", "Гара", 8);
AddStreet(city, "Площад", "Гара", 3);
AddStreet(city, "Площад", "Пазар", 9);
AddStreet(city, "Гара", "Клиент", 3);
AddStreet(city, "Пазар", "Клиент", 2);
Console.WriteLine(Dijkstra(city, "Склад").Dist["Пазар"]);
Отговор

Идеята

Остарелите записи

Когато площадът получи 3 минути вместо 5, записът „5 Площад“ вече е в опашката. Защо не го сменим на място?

Вградените опашки не могат: PriorityQueue в C# няма „смени приоритета“. Remove (от .NET 9) търси елемента линейно, O(n). Затова по-доброто време влиза като нов запис. Старият остава, а когато излезе, проверката го хвърля: времето му е по-голямо от записаното в dist. Това е мързеливо изтриване (lazy deletion).

В опашката може да има повече записи от местата, най-много по един на улица. Цената е малко памет и няколко празни вземания.

while (queue.TryDequeue(out var place, out var minutes))
{
    if () continue; // остаряло

Пробвай

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

Колега е решил, че първото намерено време е и най-доброто, както в BFS:

static Paths Dijkstra(
    Dictionary<string, List<Street>> city, string start)
{
    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 place, out var minutes))
    {
        if (minutes > dist[place]) continue; // остаряло
        foreach (Street street in city[place])
        {
            int t = minutes + street.Minutes;
            if (!dist.ContainsKey(street.To))
            {
                dist[street.To] = t;
                prev[street.To] = place;
                queue.Enqueue(street.To, t);
            }
        }
    }
    return new Paths(dist, prev);
}
var paths = Dijkstra(city, "Склад");
var r = Route(paths.Prev, "Клиент");
Console.WriteLine($"Най-бързо: {string.Join(" → ", r)} ({r.Count - 1} улици, {Minutes(city, r)} мин)");
Изход
Най-бързо: Склад → Мост → Гара → Клиент (3 улици, 13 мин)

13 минути вместо 9. На кой ред е грешката?

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

Идеята

Колко струва

Всяка улица се пробва два пъти (по веднъж от всеки край) и може да сложи запис. Всеки запис влиза и излиза веднъж, по O(log V). Общо O((V + E) log V) за V места и E улици.

Без опашка най-близкото място се търси с цикъл през всички места, които още не са окончателни. Така е написан алгоритъмът в оригинал:

static Dictionary<string, int> DijkstraScan(
    Dictionary<string, List<Street>> city, string start)
{
    var dist = city.Keys.ToDictionary(place => place, _ => int.MaxValue);
    dist[start] = 0;
    var done = new HashSet<string>();
    while (done.Count < city.Count)
    {
        string? best = null;
        foreach (string place in city.Keys)
        {
            if (done.Contains(place)) continue;
            if (best == null || dist[place] < dist[best]) best = place;
        }
        if (dist[best!] == int.MaxValue) break;
        done.Add(best!);
        foreach (Street street in city[best!])
        {
            int t = dist[best!] + street.Minutes;
            if (t < dist[street.To]) dist[street.To] = t;
        }
    }
    return dist;
}
var city = new Dictionary<string, List<Street>>();
AddStreet(city, "Склад", "Мост", 2);
AddStreet(city, "Склад", "Площад", 5);
AddStreet(city, "Склад", "Пазар", 15);
AddStreet(city, "Мост", "Площад", 1);
AddStreet(city, "Мост", "Гара", 8);
AddStreet(city, "Площад", "Гара", 3);
AddStreet(city, "Площад", "Пазар", 9);
AddStreet(city, "Гара", "Клиент", 3);
AddStreet(city, "Пазар", "Клиент", 2);
var dist = DijkstraScan(city, "Склад");
Console.WriteLine(string.Join(", ", new[] { "Склад", "Мост", "Площад", "Гара", "Пазар", "Клиент" }
    .Select(p => $"{p} {dist[p]}")));
Изход
Склад 0, Мост 2, Площад 3, Гара 6, Пазар 11, Клиент 9

Отговорът е същият. Но цикълът е V стъпки, и се прави V пъти: O(V²).

Пусни двата варианта в квартал, в който кръстовищата са в мрежа, а всяко е свързано с десния и долния си съсед. Всяка улица е от 1 до 9 минути. Брои се всяко сравнение на две времена: при търсенето на най-близкото, в опашката и при пробването на улица.

  • Без опашка: търсене на най-близкото с цикъл O(n²)
  • С приоритетна опашка O(n log n)
Алгоритъмn = 100n = 1000n = 10 000n = 100 000
Без опашка: търсене на най-близкото с цикъл5410504 372≈ 50 437 200≈ 5 043 720 000
С приоритетна опашка126917 121213 6752 554 618
Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.
static Paths Dijkstra(
    Dictionary<string, List<Street>> city, string start)
{
    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 place, out var minutes))
    {
        if (minutes > dist[place]) continue; // остаряло
        foreach (Street street in city[place])
        {
            int t = minutes + street.Minutes;
            if (!dist.TryGetValue(street.To, out int old)
                || t < old)
            {
                dist[street.To] = t;
                prev[street.To] = place;
                queue.Enqueue(street.To, t);
            }
        }
    }
    return new Paths(dist, prev);
}

При 1000 кръстовища без опашка са 504 372 сравнения, с опашка 17 121. При 100 000 кръстовища, колкото има един голям град, опашката прави 2 554 618. Без нея биха били около 5 милиарда: Bench не ги пуска, а ги оценява по кривата.

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

Кога O(V²) е по-добре? Когато графът е гъст: всяко място е свързано с почти всяко, и E е около V². Тогава опашката прави O(V² log V), а цикълът O(V²). В пътна мрежа всяко кръстовище има 3–4 улици, графът е рядък и опашката печели.

Отрицателните тегла чупят Dijkstra. Ако една улица струва −5 (да кажем, бонус за доставка по пътя), място, което вече е окончателно, може да стане по-близко през нея по-късно, а алгоритъмът вече не го поглежда. За такива графи е Bellman-Ford: той пробва всяка улица V − 1 пъти, O(V · E), и казва, ако има цикъл, който намалява времето безкрай.

Капан в Java и C#: ∞ често се пише като int.MaxValue. Ако прибавиш минути към него, числото прелива и става отрицателно: недостигнатото място изглежда най-близкото. Затова dijkstraScan спира, щом най-близкото е ∞, а dijkstra изобщо не пази ∞: липсващото място е недостигнато.

Навигацията в телефона не пуска Dijkstra върху целия континент. Ползва A*: Dijkstra, който в опашката добавя към минутите и оценка колко остава по права линия, затова върви към целта, вместо във всички посоки. Протоколът OSPF, по който рутерите в една мрежа намират пътя на пакетите, пуска истински Dijkstra.

Упражнение

Затворена улица

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

Ремонт. Улицата между моста и площада е затворена. Махни я от града (в двете посоки) и изведи най-бързия маршрут и минутите до гарата, клиента и пазара:

Изход
Гара: Склад → Площад → Гара (8 мин)
Клиент: Склад → Площад → Гара → Клиент (11 мин)
Пазар: Склад → Площад → Гара → Клиент → Пазар (13 мин)

Пазарът пак е най-бърз през клиента: 13 минути срещу 14 през площада и 15 по булеварда.

Още задачи

  • Спри навреме. Ако те интересува само клиентът, спри, щом той излезе от опашката. Колко записа остават невзети?
  • Брой вземанията. Брой колко записа са излезли от опашката и колко от тях са остарели.
  • Два куриера. Два склада, един клиент: кой куриер стига пръв? Подсказка: сложи и двата склада в опашката с 0 минути.

Тест

Провери се

1. Защо BFS не намира най-бързия маршрут, когато улиците имат минути?
2. Мястото излиза от опашката с най-малко минути от всички записи. Защо времето му е окончателно?
3. В опашката стои 5 Площад, а Площад вече има 3 минути. Какво прави алгоритъмът, когато 5 Площад излезе?
4. Колко струва Dijkstra с двоичен heap за V места и E улици?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·