From da7c511037f12b5a607cf089c12a7a75ef610046 Mon Sep 17 00:00:00 2001 From: Stoycho Kyosev Date: Wed, 4 Jan 2023 18:06:10 +0200 Subject: fix --- Seminar12/README.md | 9 ++------- 1 file changed, 2 insertions(+), 7 deletions(-) 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 -- cgit v1.3.1-26-gb76a