Website Summary Files Commits Branches @commit @diff @stats
diff options
context:
space:
mode:
Commitda7c511037f12b5a607cf089c12a7a75ef610046 (patch)
Author
 Stoycho Kyosev <stoycho.kk@gmail.com>
2023-01-04 18:06:10 +0200
Committer
 Stoycho Kyosev <stoycho.kk@gmail.com>
2023-01-04 18:06:10 +0200
Files2624a78f3dacb1c940a671c71b91c6a7d2f17f17
Data-structures-and-algorithms-da7c511037f12b5a607cf089c12a7a75ef610046.tar
Data-structures-and-algorithms-da7c511037f12b5a607cf089c12a7a75ef610046.tar.gz
Data-structures-and-algorithms-da7c511037f12b5a607cf089c12a7a75ef610046.zip
Parent46a31d1c2bfeca7429df19a5e989a52b665b0bb3 (diff)
fix
1 files changed, 2 insertions, 7 deletions
-rw-r--r--Seminar12/README.md9
diff --git a/Seminar12/README.md b/Seminar12/README.md
index 2337958..5f6f113 100644
--- a/Seminar12/README.md
+++ b/Seminar12/README.md
@@ -1,5 +1,5 @@
# Най - къси пътища в граф.
-Обобщение: Разглеждаме накратко структурата от данни приоритетна опашка.
+Обобщение: Разглеждаме накратко структурата от данни приоритетна опашка. Разглеждаме алгоритъма на Dijkstra и функцията relax.
## Приоритетни опашки, но накратко
В първата част на курса се запознахме със структурата от данни опашка. В приоритетната опашка отново можем да вкарваме и изваждаме елементи, но този път не излиза най - рано добавения елемент. Всеки елемент има приоритет и когато извадим елемент излиза най - приоритетния. Примерно, ако елементите ни са цели числа, можем да кажем, че колкото по - малък е един елемент толкова по - малък приоритет има той.
@@ -134,9 +134,4 @@ relax(u, v):
Използваме std::list понеже добавянето в началото е бързо, но със същия успех бихме могли да добавяме в края на вектор примерно и да го обърнем след това.
-Ако искаме най - късите пътища от s до всички достижими върхове, просто ще изчакаме алгоритъма да приключи. След това ще върнем distances и parent за да можем да възстановим пътя за всеки връх.
-
-## Сложност
-Ако търсим най - къси пътища в нетегловен граф няма нужда да използваме Dijkstra. Един прост bfs би ни свършил работа.
-
-Сложността на Dijkstra зависи от реализацията на приоритетната опашка, която използваме. \ No newline at end of file
+Ако искаме най - късите пътища от s до всички достижими върхове, просто ще изчакаме алгоритъма да приключи. След това ще върнем distances и parent за да можем да възстановим пътя за всеки връх. \ No newline at end of file