diff options
fix
1 files changed, 2 insertions, 7 deletions
| -rw-r--r-- | Seminar12/README.md | 9 |
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 |
