diff options
changes
1 files changed, 14 insertions, 5 deletions
| -rw-r--r-- | Seminar12/README.md | 19 |
diff --git a/Seminar12/README.md b/Seminar12/README.md index 5f6f113..32ff2d4 100644 --- a/Seminar12/README.md +++ b/Seminar12/README.md @@ -34,6 +34,8 @@ int main() { Изваждането на елемент от приоритетната опашка е със сложност O(log(n)) където n e броя на елементите в опашката. Също така можем да построим приоритетна опашка в O(n) време. +Приоритетните опашки често имат операцията decrease-key. Ако приоритетната опашка е от двойки ключ и стойност искаме да намалим ключа на дадена стойност. Тази операция е O(log(n)). + ## Алгоритъм на Dijkstra Алгоритъмът на Dijkstra намира най - къс път в ориентиран граф. **Алгоритъмът на Dijkstra не работи коректно, ако има отрицателни тегла, дори да няма отрицателни цикли!** @@ -124,14 +126,21 @@ relax(u, v): Създаваме приоритетна опашка в която ще държим наредени двойки от типа (връх, тегло на най - къс път). -Всеки път от тази опашка ще вадим **върхът с най - лек път**. Затова съзваме структурата, представляваща двойка. В приоритетната опашка тя ще представлява приоритета на всеки връх. Оригиналния алгоритъм зарежда в приоритетната опашка веднага всички върхове и ъпдейтва ключовете им директно в опашката. +Всеки път от тази опашка ще вадим **върхът с най - лек път**. Затова съзваме структурата, представляваща двойка. В приоритетната опашка пътят от старта до върха ще представлява приоритета на върха. Оригиналният алгоритъм зарежда в приоритетната опашка веднага всички върхове и ъпдейтва ключовете им директно в опашката чрез функцията decrease-key. В началото всички ключове без началния са INT_MAX и след това постепенно се прилага decrease key всеки път когато открием по - кратък път. Тук приемаме друг подход, постепенно добавяме върхове в опашката, понеже std::priority_queue не поддържа decrease key. Това ще доведе до добавяне на върха няколко пъти в опашката но с различни ключове (всеки път когато намерим по - къс път). Това обаче не прави алгоритъма некоректен, просто върти малко повече. -Сега, докато има елементи в опашката вземаме най - лекия връх v. За всеки негов съсед u, ако можем да го релаксираме го добавяме в опашката с разстоянието, което сме намерили. +Сега, докато има елементи в опашката вземаме най - лекия връх v (този с минимален ключ т.е. с най - малък открит път от старта до него). За всеки негов съсед u, ако можем да го релаксираме го добавяме в опашката с разстоянието, което сме намерили. -Когато върхът, който извадим от опашката е end в distances[end] e записан най - късия път от началото до end. Това твърдение също не е очевидно, но е вярно. +Когато върхът, който извадим от опашката е end в distances[end] e записан най - късия път от началото до end. Това твърдение също не е очевидно, но е вярно. Та, когато извадим end от опашката ни остава само да възстановим пътя и да върнем неговата стойност. Извеждаме го на стандартния изход, понеже това е примерен код. След това връщаме и самата дължина. -Използваме std::list понеже добавянето в началото е бързо, но със същия успех бихме могли да добавяме в края на вектор примерно и да го обърнем след това. +Използваме std::list понеже добавянето в началото е бързо, но със същия успех бихме могли да добавяме в края на вектор примерно и да го обърнем след това. + +Ако искаме най - късите пътища от s до всички достижими върхове, просто ще изчакаме алгоритъма да приключи. След това ще върнем distances и parent за да можем да възстановим пътя за всеки връх. + +Сложността на представената версия на Dijkstra е O(|E|log(|E|)). Сложността на оригиналната Dijkstra реализирана с binary heap е +O(|V|log|V| + |E|log|V|) +* |V|*log(|V|) - в началото добавяме |V| елемента в приоритетната опашка. Всяко добавяне е log(|V|) време +* |E|log|V| - Можем да имаме |E| операции decrease key (ако релаксираме за всяко ребро). Всеки decrease-key е log|V|. -Ако искаме най - късите пътища от s до всички достижими върхове, просто ще изчакаме алгоритъма да приключи. След това ще върнем distances и parent за да можем да възстановим пътя за всеки връх.
\ No newline at end of file +С изтънчени структури от данни Dijkstra може да стане и по - бърза **асимптотично**.
\ No newline at end of file |
