Dijkstra
Накратко: Алгоритъмът на Dijkstra намира най-кратките пътища от един връх в граф с неотрицателни тегла, като взима най-близкия връх от приоритетна опашка: O((V + E) log V).
Проблем
Най-малко улици не е най-бързо
Куриерът тръгва от склада към клиент. Приложението трябва да му даде най-бързия маршрут. Всяка улица има време в минути: булевардът е широк, но в задръстване, а малките улички са бързи.
Градът е граф, улиците са ребрата му в двете посоки (виж представянето на граф):
def add_street(city, a, b, minutes): city.setdefault(a, []).append((b, minutes)) city.setdefault(b, []).append((a, minutes))city = {}add_street(city, "Склад", "Мост", 2)add_street(city, "Склад", "Площад", 5)add_street(city, "Склад", "Пазар", 15)add_street(city, "Мост", "Площад", 1)add_street(city, "Мост", "Гара", 8)add_street(city, "Площад", "Гара", 3)add_street(city, "Площад", "Пазар", 9)add_street(city, "Гара", "Клиент", 3)add_street(city, "Пазар", "Клиент", 2)Първата идея е BFS от предишния урок: той намира най-късия път. Но BFS брои улиците, не минутите:
def fewest_streets(city, start): prev = {} seen = {start} queue = deque([start]) while queue: place = queue.popleft() for to, _ in city[place]: if to not in seen: seen.add(to) prev[to] = place queue.append(to) return prevcity = {}add_street(city, "Склад", "Мост", 2)add_street(city, "Склад", "Площад", 5)add_street(city, "Склад", "Пазар", 15)add_street(city, "Мост", "Площад", 1)add_street(city, "Мост", "Гара", 8)add_street(city, "Площад", "Гара", 3)add_street(city, "Площад", "Пазар", 9)add_street(city, "Гара", "Клиент", 3)add_street(city, "Пазар", "Клиент", 2)r = route(fewest_streets(city, "Склад"), "Клиент")print(f"Най-малко улици: {' → '.join(r)} ({len(r) - 1} улици, {minutes(city, r)} мин)")Най-малко улици: Склад → Пазар → Клиент (2 улици, 17 мин)Две улици, но 17 минути: 15 по булеварда до пазара и 2 до клиента. През моста, площада и гарата са четири улици и само 9 минути. BFS дори не гледа минутите.
Идеята
Най-близкото място първо
BFS обхожда по брой улици: първо всичко на една улица, после на две. Тук трябва да обхождаш по минути: първо мястото, до което се стига най-бързо, после следващото.
Това прави алгоритъмът на Dijkstra (Едсхер Дейкстра, 1956). Пази за всяко място най-доброто време досега, dist, и опашка от записи „минути, място“.
- Отначало
distе 0 за склада, а всяко друго място е недостигнато (∞). - Вземи от опашката записа с най-малко минути. Това е приоритетна опашка: вади най-малкото за O(log n).
- За всяка улица от това място пробвай: стига ли се по нея до съседа по-бързо от досегашното? Ако да, запиши новото време, запомни откъде си дошъл (
prev) и сложи нов запис в опашката. Това пробване се казва релаксация (relaxation). - Повтаряй, докато опашката свърши.
Защо мястото, което излиза от опашката, вече има окончателното си време? Всички други записи са с поне толкова минути, а всяка улица добавя минути. Никой път през тях не може да стигне по-рано.
Виж го
Dijkstra отвътре
def dijkstra(city, start): dist = {start: 0} prev = {} queue = [(0, start)] while queue: minutes, place = heapq.heappop(queue) if minutes > dist[place]: continue # остаряло for to, length in city[place]: t = minutes + length if to not in dist or t < dist[to]: dist[to] = t prev[to] = place heapq.heappush(queue, (t, to)) return dist, prevheapq сравнява кортежите отляво надясно: (минути, място) излиза по минути. Място, което го няма в dist, още не е достигнато: това е ∞.prev пази маршрута отзад напред: за всяко място, откъде е дошъл най-бързият път. Тръгваш от клиента, следваш prev до склада и обръщаш:
def route(prev, end): places = [] at = end while at is not None: places.append(at) at = prev.get(at) return places[::-1]dist, prev = dijkstra(city, "Склад")r = route(prev, "Клиент")print(f"Най-бързо: {' → '.join(r)} ({len(r) - 1} улици, {minutes(city, r)} мин)")Най-бързо: Склад → Мост → Площад → Гара → Клиент (4 улици, 9 мин)def dijkstra(city, start): dist = {start: 0} prev = {} queue = [(0, start)] while queue: minutes, place = heapq.heappop(queue) if minutes > dist[place]: continue # остаряло for to, length in city[place]: t = minutes + length if to not in dist or t < dist[to]: dist[to] = t prev[to] = place heapq.heappush(queue, (t, to)) return dist, prevСтъпка по стъпка, с думи
- Куриерът тръгва от Склад: 0 минути. Всяко друго място е ∞, още нищо не го е стигнало. В опашката има един запис: 0 Склад.
- Взима се най-малкият запис, 0 Склад. Всяка улица от него дава време: Мост 2, Площад 5, Пазар 15. Всички са по-добри от ∞: записват се и влизат в опашката.
- Следва 2 Мост. През него Площад е 2 + 1 = 3, по-добро от 5: времето и prev се сменят, влиза 3 Площад. Старото 5 Площад остава в опашката, вече е остаряло. Гара получава 10.
- 3 Площад: окончателно, нищо в опашката не може да го направи по-бързо. През него Гара пада от 10 на 6, а Пазар от 15 на 12.
- Отгоре е 5 Площад, но Площад вече има 3. Записът е остарял: прескача се. Това е мързеливото изтриване: вместо да търсиш стария запис в опашката, го изхвърляш, когато излезе.
- 6 Гара: окончателно. Клиент получава 6 + 3 = 9. Обратно към Мост с 14 и Площад с 9 не е по-добре.
- 9 Клиент: окончателно, 9 минути. През Клиент Пазар пада от 12 на 11. Границата расте по време, а не по брой улици.
- Останалото: 10 Гара е остаряло, 11 Пазар е окончателно и не подобрява нищо, 12 и 15 Пазар са остарели. Опашката е празна.
- prev дава маршрута отзад напред: Клиент ← Гара ← Площад ← Мост ← Склад. Обърнат: Склад → Мост → Площад → Гара → Клиент, 9 минути, четири улици. Маршрутът с две улици през Пазар е 17.
Местата стават окончателни по реда на времето си: Склад 0, Мост 2, Площад 3, Гара 6, Клиент 9, Пазар 11. Пазарът, който е на една улица от склада, е последен.
Пробвай
Предвиди изхода
Колко минути до пазара дава Dijkstra?
city = {}add_street(city, "Склад", "Мост", 2)add_street(city, "Склад", "Площад", 5)add_street(city, "Склад", "Пазар", 15)add_street(city, "Мост", "Площад", 1)add_street(city, "Мост", "Гара", 8)add_street(city, "Площад", "Гара", 3)add_street(city, "Площад", "Пазар", 9)add_street(city, "Гара", "Клиент", 3)add_street(city, "Пазар", "Клиент", 2)dist, prev = dijkstra(city, "Склад")print(dist["Пазар"])Идеята
Остарелите записи
Когато площадът получи 3 минути вместо 5, записът „5 Площад“ вече е в опашката. Защо не го сменим на място?
Вградените опашки не могат: heapq в Python е само функции върху списък, без „смени приоритета“. Затова по-доброто време влиза като нов запис. Старият остава, а когато излезе, проверката го хвърля: времето му е по-голямо от записаното в dist. Това е мързеливо изтриване (lazy deletion).
В опашката може да има повече записи от местата, най-много по един на улица. Цената е малко памет и няколко празни вземания.
minutes, place = heapq.heappop(queue)
if :
continue # остарялоЗаписът е остарял, ако минутите му са повече от най-доброто време на мястото. Тогава някой по-ранен запис вече е обработил мястото с по-малко минути.
Пробвай
Намери грешката
Колега е решил, че първото намерено време е и най-доброто, както в BFS:
def dijkstra(city, start): dist = {start: 0} prev = {} queue = [(0, start)] while queue: minutes, place = heapq.heappop(queue) if minutes > dist[place]: continue # остаряло for to, length in city[place]: t = minutes + length if to not in dist: dist[to] = t prev[to] = place heapq.heappush(queue, (t, to)) return dist, prevdist, prev = dijkstra(city, "Склад")r = route(prev, "Клиент")print(f"Най-бързо: {' → '.join(r)} ({len(r) - 1} улици, {minutes(city, r)} мин)")Най-бързо: Склад → Мост → Гара → Клиент (3 улици, 13 мин)13 минути вместо 9. На кой ред е грешката?
Избери реда с грешката.
Времето се записва само първия път, когато мястото е достигнато. Площадът получава 5 директно от склада, и когато мостът намери 3, то не се записва. Пробването трябва да сравнява: to not in dist or t < dist[to]. Първото време е окончателно в BFS, защото там всяка улица струва еднакво.
Идеята
Колко струва
Всяка улица се пробва два пъти (по веднъж от всеки край) и може да сложи запис. Всеки запис влиза и излиза веднъж, по O(log V). Общо O((V + E) log V) за V места и E улици.
Без опашка най-близкото място се търси с цикъл през всички места, които още не са окончателни. Така е написан алгоритъмът в оригинал:
def dijkstra_scan(city, start): dist = {place: math.inf for place in city} dist[start] = 0 done = set() while len(done) < len(city): best = None for place in city: if place not in done and (best is None or dist[place] < dist[best]): best = place if dist[best] == math.inf: break done.add(best) for to, length in city[best]: t = dist[best] + length if t < dist[to]: dist[to] = t return distcity = {}add_street(city, "Склад", "Мост", 2)add_street(city, "Склад", "Площад", 5)add_street(city, "Склад", "Пазар", 15)add_street(city, "Мост", "Площад", 1)add_street(city, "Мост", "Гара", 8)add_street(city, "Площад", "Гара", 3)add_street(city, "Площад", "Пазар", 9)add_street(city, "Гара", "Клиент", 3)add_street(city, "Пазар", "Клиент", 2)dist = dijkstra_scan(city, "Склад")print(", ".join(f"{p} {dist[p]}" for p in ["Склад", "Мост", "Площад", "Гара", "Пазар", "Клиент"]))Склад 0, Мост 2, Площад 3, Гара 6, Пазар 11, Клиент 9Отговорът е същият. Но цикълът е V стъпки, и се прави V пъти: O(V²).
Пусни двата варианта в квартал, в който кръстовищата са в мрежа, а всяко е свързано с десния и долния си съсед. Всяка улица е от 1 до 9 минути. Брои се всяко сравнение на две времена: при търсенето на най-близкото, в опашката и при пробването на улица.
- Без опашка: търсене на най-близкото с цикъл
O(n²) - С приоритетна опашка
O(n log n)
| Алгоритъм | n = 100 | n = 1000 | n = 10 000 | n = 100 000 |
|---|---|---|---|---|
| Без опашка: търсене на най-близкото с цикъл | 5410 | 504 372 | ≈ 50 437 200 | ≈ 5 043 720 000 |
| С приоритетна опашка | 1269 | 17 121 | 213 675 | 2 554 618 |
def dijkstra(city, start): dist = {start: 0} prev = {} queue = [(0, start)] while queue: minutes, place = heapq.heappop(queue) if minutes > dist[place]: continue # остаряло for to, length in city[place]: t = minutes + length if to not in dist or t < dist[to]: dist[to] = t prev[to] = place heapq.heappush(queue, (t, to)) return 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), и казва, ако има цикъл, който намалява времето безкрай.
В Python ∞ еmath.inf: math.inf + 5 е пак math.inf, а целите числа нямат препълване. В Java и C# ∞ обикновено е най-голямото int, и прибавянето на минути към него дава отрицателно число.Навигацията в телефона не пуска Dijkstra върху целия континент. Ползва A*: Dijkstra, който в опашката добавя към минутите и оценка колко остава по права линия, затова върви към целта, вместо във всички посоки. Протоколът OSPF, по който рутерите в една мрежа намират пътя на пакетите, пуска истински Dijkstra.
Упражнение
Затворена улица
Реши задачата в редактора си.
Ремонт. Улицата между моста и площада е затворена. Махни я от града (в двете посоки) и изведи най-бързия маршрут и минутите до гарата, клиента и пазара:
Гара: Склад → Площад → Гара (8 мин)Клиент: Склад → Площад → Гара → Клиент (11 мин)Пазар: Склад → Площад → Гара → Клиент → Пазар (13 мин)Пазарът пак е най-бърз през клиента: 13 минути срещу 14 през площада и 15 по булеварда.
Още задачи
- Спри навреме. Ако те интересува само клиентът, спри, щом той излезе от опашката. Колко записа остават невзети?
- Брой вземанията. Брой колко записа са излезли от опашката и колко от тях са остарели.
- Два куриера. Два склада, един клиент: кой куриер стига пръв? Подсказка: сложи и двата склада в опашката с 0 минути.
Тест