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

Dijkstra

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

Проблем

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

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

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

static void addStreet(Map<String, List<Street>> city,
        String a, String b, int minutes) {
    city.computeIfAbsent(a, k -> new ArrayList<>()).add(new Street(b, minutes));
    city.computeIfAbsent(b, k -> new ArrayList<>()).add(new Street(a, minutes));
}
Map<String, List<Street>> city = new HashMap<>();
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 Map<String, String> fewestStreets(
        Map<String, List<Street>> city, String start) {
    Map<String, String> prev = new HashMap<>();
    Set<String> seen = new HashSet<>(Set.of(start));
    Deque<String> queue = new ArrayDeque<>(List.of(start));
    while (!queue.isEmpty()) {
        String place = queue.poll();
        for (Street street : city.get(place)) {
            if (seen.add(street.to())) {
                prev.put(street.to(), place);
                queue.add(street.to());
            }
        }
    }
    return prev;
}
Map<String, List<Street>> city = new HashMap<>();
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);
List<String> r = route(fewestStreets(city, "Склад"), "Клиент");
System.out.println("Най-малко улици: " + String.join(" → ", r) + " (" + (r.size() - 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(
        Map<String, List<Street>> city, String start) {
    Map<String, Integer> dist = new HashMap<>();
    Map<String, String> prev = new HashMap<>();
    var queue = new PriorityQueue<Stop>(
            Comparator.comparingInt(Stop::minutes));
    dist.put(start, 0);
    queue.add(new Stop(start, 0));
    while (!queue.isEmpty()) {
        Stop stop = queue.poll();
        if (stop.minutes() > dist.get(stop.place())) {
            continue; // остаряло
        }
        for (Street street : city.get(stop.place())) {
            int t = stop.minutes() + street.minutes();
            Integer old = dist.get(street.to());
            if (old == null || t < old) {
                dist.put(street.to(), t);
                prev.put(street.to(), stop.place());
                queue.add(new Stop(street.to(), t));
            }
        }
    }
    return new Paths(dist, prev);
}
PriorityQueue с Comparator.comparingInt(Stop::minutes) вади записа с най-малко минути. old == null значи, че мястото още не е достигнато: това е ∞.

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

static List<String> route(Map<String, String> prev, String end) {
    List<String> places = new ArrayList<>();
    for (String at = end; at != null; at = prev.get(at)) places.add(at);
    Collections.reverse(places);
    return places;
}
Paths paths = dijkstra(city, "Склад");
List<String> r = route(paths.prev(), "Клиент");
System.out.println("Най-бързо: " + String.join(" → ", r) + " (" + (r.size() - 1) + " улици, " + minutes(city, r) + " мин)");
Изход
Най-бързо: Склад → Мост → Площад → Гара → Клиент (4 улици, 9 мин)

static Paths dijkstra(
        Map<String, List<Street>> city, String start) {
    Map<String, Integer> dist = new HashMap<>();
    Map<String, String> prev = new HashMap<>();
    var queue = new PriorityQueue<Stop>(
            Comparator.comparingInt(Stop::minutes));
    dist.put(start, 0);
    queue.add(new Stop(start, 0));
    while (!queue.isEmpty()) {
        Stop stop = queue.poll();
        if (stop.minutes() > dist.get(stop.place())) {
            continue; // остаряло
        }
        for (Street street : city.get(stop.place())) {
            int t = stop.minutes() + street.minutes();
            Integer old = dist.get(street.to());
            if (old == null || t < old) {
                dist.put(street.to(), t);
                prev.put(street.to(), stop.place());
                queue.add(new Stop(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?

Map<String, List<Street>> city = new HashMap<>();
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);
System.out.println(dijkstra(city, "Склад").dist().get("Пазар"));
Отговор

Идеята

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

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

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

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

Stop stop = queue.poll();
if () {
    continue; // остаряло
}

Пробвай

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

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

static Paths dijkstra(
        Map<String, List<Street>> city, String start) {
    Map<String, Integer> dist = new HashMap<>();
    Map<String, String> prev = new HashMap<>();
    var queue = new PriorityQueue<Stop>(
            Comparator.comparingInt(Stop::minutes));
    dist.put(start, 0);
    queue.add(new Stop(start, 0));
    while (!queue.isEmpty()) {
        Stop stop = queue.poll();
        if (stop.minutes() > dist.get(stop.place())) {
            continue; // остаряло
        }
        for (Street street : city.get(stop.place())) {
            int t = stop.minutes() + street.minutes();
            Integer old = dist.get(street.to());
            if (old == null) {
                dist.put(street.to(), t);
                prev.put(street.to(), stop.place());
                queue.add(new Stop(street.to(), t));
            }
        }
    }
    return new Paths(dist, prev);
}
Paths paths = dijkstra(city, "Склад");
List<String> r = route(paths.prev(), "Клиент");
System.out.println("Най-бързо: " + String.join(" → ", r) + " (" + (r.size() - 1) + " улици, " + minutes(city, r) + " мин)");
Изход
Най-бързо: Склад → Мост → Гара → Клиент (3 улици, 13 мин)

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

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

Идеята

Колко струва

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

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

static Map<String, Integer> dijkstraScan(
        Map<String, List<Street>> city, String start) {
    Map<String, Integer> dist = new HashMap<>();
    for (String place : city.keySet()) dist.put(place, Integer.MAX_VALUE);
    dist.put(start, 0);
    Set<String> done = new HashSet<>();
    while (done.size() < city.size()) {
        String best = null;
        for (String place : city.keySet()) {
            if (done.contains(place)) continue;
            if (best == null || dist.get(place) < dist.get(best)) best = place;
        }
        if (dist.get(best) == Integer.MAX_VALUE) break;
        done.add(best);
        for (Street street : city.get(best)) {
            int t = dist.get(best) + street.minutes();
            if (t < dist.get(street.to())) dist.put(street.to(), t);
        }
    }
    return dist;
}
Map<String, List<Street>> city = new HashMap<>();
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);
Map<String, Integer> dist = dijkstraScan(city, "Склад");
System.out.println(String.join(", ", Stream.of("Склад", "Мост", "Площад", "Гара", "Пазар", "Клиент")
        .map(p -> p + " " + dist.get(p)).toList()));
Изход
Склад 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(
        Map<String, List<Street>> city, String start) {
    Map<String, Integer> dist = new HashMap<>();
    Map<String, String> prev = new HashMap<>();
    var queue = new PriorityQueue<Stop>(
            Comparator.comparingInt(Stop::minutes));
    dist.put(start, 0);
    queue.add(new Stop(start, 0));
    while (!queue.isEmpty()) {
        Stop stop = queue.poll();
        if (stop.minutes() > dist.get(stop.place())) {
            continue; // остаряло
        }
        for (Street street : city.get(stop.place())) {
            int t = stop.minutes() + street.minutes();
            Integer old = dist.get(street.to());
            if (old == null || t < old) {
                dist.put(street.to(), t);
                prev.put(street.to(), stop.place());
                queue.add(new Stop(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#: ∞ често се пише като Integer.MAX_VALUE. Ако прибавиш минути към него, числото прелива и става отрицателно: недостигнатото място изглежда най-близкото. Затова 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 за достъпно обучение по програмиране ·