Website Summary Files Commits Branches @commit @diff @stats
diff options
context:
space:
mode:
Commit65828489b8bf215bd4ed9cac20113c2a3f598e33 (patch)
Author
 Stoycho Kyosev <stoycho.kk@gmail.com>
2023-01-04 18:21:46 +0200
Committer
 Stoycho Kyosev <stoycho.kk@gmail.com>
2023-01-04 18:21:46 +0200
Filesbe3ed5023be870aa2d6c3803d01b2ee848cdfc99
Data-structures-and-algorithms-65828489b8bf215bd4ed9cac20113c2a3f598e33.tar
Data-structures-and-algorithms-65828489b8bf215bd4ed9cac20113c2a3f598e33.tar.gz
Data-structures-and-algorithms-65828489b8bf215bd4ed9cac20113c2a3f598e33.zip
Parentda7c511037f12b5a607cf089c12a7a75ef610046 (diff)
changes
1 files changed, 14 insertions, 5 deletions
-rw-r--r--Seminar12/README.md19
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