Add seminar 12

9 files changed, 494 insertions, 5 deletions

diff --git a/Seminar08/README.md b/Seminar08/README.md
index 9948c59..2243f09 100644
--- a/Seminar08/README.md
+++ b/Seminar08/README.md
@@ -120,7 +120,7 @@ bool isLeaf(const Tree<T>* t) {
 Разглеждаме масив tArray с *n* елемента за който е вярно: **В tArray[i] е записан номера на бащата на връх с номер i. Ако върхът с номер i е корен (а корена няма баща) просто пишем -1**.
 Дървото от пример 1 може да се представи чрез списък на бащите по следния начин:
 
-* [-1, 0, 0, 2, 2, 3, 3, 3]
+* [-1, 0, 0, 2, 2, 3, 3, 4]
 
 Едно от предимствата на това представяне е, че можем да представим дърво с произволна разклоненост. Все пак няма значение разклонеността, ако можем да номерираме възлите с числа от 0 до *n-1* можем да го представим по този начин.
 
diff --git a/Seminar11/DFS-Additional.cpp b/Seminar11/DFS-Additional.cpp
new file mode 100644
index 0000000..a5022e3
--- /dev/null
+++ b/Seminar11/DFS-Additional.cpp
@@ -0,0 +1,200 @@
+// Малко допълнителни неща покрай дфс ако ви е интересно.
+#include<iostream>
+#include"Graph-Impl/AdjacencyListGraph/AdjListGraph.h"
+#include"Graph-Impl/MatrixGraph/MatrixGraph.h"
+#include<vector>
+#include<algorithm>
+
+using std::vector;
+using vertex_t = AdjListGraph::vertex_t; // Типа представящ връх в графа
+
+class DFSExamples {
+private:
+    vector<size_t> in;
+    vector<size_t> out;
+    vector<vertex_t> parent;
+
+public:
+
+void DFS_Visit(const AdjListGraph& g, size_t& time, vertex_t s) {
+    in[s] = time;
+    time++;
+
+    const auto& adj = g.adjacent(s);
+
+    for(const auto& v : adj) {
+        if(in[v.to] == -1) {
+            parent[v.to] = s;
+            DFS_Visit(g, time, v.to);
+        }
+    }
+
+    time++;
+    out[s] = time;
+}
+
+void DFS(const AdjListGraph& g, bool showDetails) {
+    // Нека си представим, че имаме време. Всяка стъпка на алгоритъма отнема една единица време.
+    size_t time = 0;
+
+    // Всеки връх бива открит в някакво време. Нека в този масив записваме кога е бил открит всеки връх.
+    in = vector(g.vertexCount(), (size_t)(-1));
+
+    // С всеки връх приключваме по някое време. Той няма повече непосетени съседи и спираме да се интересуваме от него.
+    // Нека в този масив записваме кога се случва това.
+    out = vector(g.vertexCount(), (size_t)(-1));
+
+    // std::vector<bool> visited(g.vertexCount(), false); 
+    // - от този масив вече нямаме нужда. Връх v e посетен когато in[v] != -1.
+
+    // Също така в примера видяхме, че DFS прави дърво. Нека си запазим това дърво.
+    // Тук стандартното представяне на дърво е неудобно, затова ще представяме дървото като масив от бащите.
+    // Примомняне: Ако v e връх parent[v] е бащата на v или -1 ако v e корен.
+    parent = vector(g.vertexCount(), (vertex_t)(-1));
+
+    // За всеки връх
+    for (vertex_t i = 0; i < g.vertexCount(); i++)
+        if(in[i] == -1) // Ако не е посетен
+            DFS_Visit(g, time, i); // Посети го и посети всички върхове достижими от него
+    
+    // Да видим какво имаме
+    if(showDetails) {
+        for (vertex_t i = 0; i < g.vertexCount(); i++) {
+            std::cout << "Vertex " << i << std::endl;
+            std::cout 
+             << "Discovered at: " << in[i] << std::endl
+             << "Finished at: "   << out[i] << std::endl 
+             << "Parent: "        << parent[i] << std::endl << std::endl;
+        }
+    }
+}
+
+void DFS_Visit_Tsort(const MatrixGraph g, size_t& time, vertex_t s) {
+    in[s] = time;
+    time++;
+
+    const auto& adj = g.adjacent(s);
+
+    for(const auto& v : adj) {
+        if(in[v] == -1) {
+            parent[v] = s;
+            DFS_Visit_Tsort(g, time, v);
+        }
+    }
+
+    time++;
+    out[s] = time;
+}
+
+// Топологически сортировки, Job scheduling
+// Защо са ни тези масиви in и out? Те ни дават информация, която можем да използваме за други интересни алгоритми.
+// Ще оставим подробното им разглеждане на други курсове, тук само ще разгледаме един бърз пример.
+
+// Нека си представим, че имаме някакви задачи за вършене. Абсолютно вероятно е някои от тези задачи да зависят от други.
+// Примерно, не мога да кандидатствам за университет ако преди това нямам диплома за завършен 12 клас
+// (въпреки, че май е възможно в някои нови български университети).
+// 
+// Можем да си представим задачите като върхове, а това, че задача А трябва да се изпълни преди задача Б да 
+// бележим чрез ориентирано ребро А -> Б.
+// 
+// Искам така да си подредя задачите, че да ги изпълня без да нарушавам зависимостите.
+// 
+// Твърдя, че ако пусна DFS, и сортирам върховете по out стойности в намаляващ ред това решава задачата ми.
+//
+// Накратко, защо това е вярно?
+// Нека имам V -> U. Има два случая, или да открия V преди U или да открия U преди V.
+//
+// 1. Откривам V преди U. Да де, но имам ребро от V към U, Следователно ще открия и финализирам U преди да финализирам V.
+// Сега out[U] > out[V] и не нарушавам зависимостите.
+// 2. Ако открия U преди V, ще финализирам U преди да стигна до V. В графа няма цикли и ако имаше път от U -> V това би затворило цикъл.
+// Тоест ще финализирам U преди да открия V. От тук следва, че out[U] > in[V] > out[V], което отново влече наредба, която не нарушава зависимостите.
+// Няма други случаи. 
+
+void DFS_Tsort(const MatrixGraph& g) {
+    size_t time = 0;
+
+    in = vector(g.vertexCount(), (size_t)(-1));
+    out = vector(g.vertexCount(), (size_t)(-1));
+    parent = vector(g.vertexCount(), (vertex_t)(-1));
+
+    for (vertex_t i = 0; i < g.vertexCount(); i++)
+        if(in[i] == -1)
+            DFS_Visit_Tsort(g, time, i);
+    
+    std::vector<std::pair<vertex_t, size_t>> result(g.vertexCount());
+
+    for (vertex_t i = 0; i < g.vertexCount(); i++)
+        result[i] = {i, out[i]};
+    
+    auto comp = [](std::pair<vertex_t, size_t>& fst, std::pair<vertex_t, size_t>& snd) -> bool {
+        return fst.second > snd.second;
+    };
+
+    std::sort(result.begin(), result.end(), comp);
+
+    for(const auto& vertexOutPair : result)
+        std::cout << vertexOutPair.first << " ";
+}
+
+// Използвам матричния, понеже той е ориентиран.
+void tsort(const MatrixGraph& g) {
+    size_t time = 0;
+
+    // Нулираме масивите
+    in = vector(g.vertexCount(), (size_t)(-1));
+    out = vector(g.vertexCount(), (size_t)(-1));
+    parent = vector(g.vertexCount(), (vertex_t)(-1));
+
+    DFS_Tsort(g);
+}
+};
+
+int main() {
+    DFSExamples d;
+
+    // Нека си вземем графа от примера
+    // Там върховете са номерирани от 1 до 12
+    // Тук от 0 до 11
+    AdjListGraph g(12);
+
+    g.addEdge(0, 2, 1);
+    g.addEdge(0, 4, 1);
+    g.addEdge(0, 5, 1);
+    g.addEdge(0, 8, 1);
+
+    g.addEdge(1, 7, 1);
+    g.addEdge(1, 3, 1);
+
+    g.addEdge(2, 4, 1);
+    g.addEdge(2, 5, 1);
+    g.addEdge(2, 6, 1);
+    g.addEdge(2, 7, 1);
+
+    g.addEdge(3, 9, 1);
+
+    g.addEdge(4, 6, 1);
+
+    g.addEdge(8, 11, 1);
+    g.addEdge(8, 10, 1);
+
+    g.addEdge(10, 11, 1);
+
+    d.DFS(g, true);
+
+    // Пример за топосортировка
+    MatrixGraph tsort(9);
+
+
+    // https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/resources/mit6_006f11_lec14_orig/
+    // Този граф е взет от линка и е на страница 5.
+    tsort.addDirectedEdge(5, 3, 1);
+    tsort.addDirectedEdge(4, 3, 1);
+    tsort.addDirectedEdge(4, 2, 1);
+    tsort.addDirectedEdge(2, 1, 1);
+    tsort.addDirectedEdge(1, 0, 1);
+    tsort.addDirectedEdge(7, 2, 1);
+    tsort.addDirectedEdge(7, 6, 1);
+    tsort.addDirectedEdge(6, 1, 1);
+
+    d.DFS_Tsort(tsort);
+}
\ No newline at end of file
diff --git a/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.cpp b/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.cpp
index bf155a1..b5835f8 100644
--- a/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.cpp
+++ b/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.cpp
@@ -87,6 +87,11 @@ std::vector<vertex_t> MatrixGraph::getPredecessors(vertex_t from) const {
     return result;
 }
 
+std::vector<vertex_t> MatrixGraph::adjacent(vertex_t from) const {
+    return getSuccessors(from);
+}
+
+
 size_t MatrixGraph::vertexCount() const {
     return data.size();
 }
\ No newline at end of file
diff --git a/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.h b/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.h
index 1e4ec71..aade1a1 100644
--- a/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.h
+++ b/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.h
@@ -45,6 +45,8 @@ class MatrixGraph {
 
     std::vector<vertex_t> getSuccessors(vertex_t) const;
     std::vector<vertex_t> getPredecessors(vertex_t) const;
+    // Same as getSuccessors, here for interface purposes.
+    std::vector<vertex_t> adjacent(vertex_t) const; 
 };
 
 #endif
\ No newline at end of file
diff --git a/Seminar11/README.md b/Seminar11/README.md
index cf0d36c..7f28913 100644
--- a/Seminar11/README.md
+++ b/Seminar11/README.md
@@ -142,4 +142,46 @@ matrix[7][5] = false
 
 Предимството на тази реализация е, че бързо можем да добавяме върхове и ребра. Също така паметта ни вече не е O(|V|^2) а O(|V| + |E|).
 
-Част от материалите са взаимствани от [тук](https://github.com/MariaGrozdeva/Data_structures_and_algorithms_FMI/tree/main/Sem_10)
\ No newline at end of file
+Част от материалите са взаимствани от [тук](https://github.com/MariaGrozdeva/Data_structures_and_algorithms_FMI/tree/main/Sem_10)
+
+## BFS
+Breadth-first search е сравнително прост алгоритъм за търсене в граф, но върху идеята, която той носи се базират други алгоритми върху графи. Примерно, алгоритъмът на Прим за минимално покриващо дърво, алгоритъмът на Dijkstra за най - къси пътища се базират на идеи подобни на тази на BFS.
+
+Като вход получаваме граф G = (V, E) и връх s BFS систематично открива всички върхове, които са достижими от s. Чрез него можем да изчислим разстоянието (най - малкия брой ребра) от s до всеки друг връх. Алгоритъма работи за ориентирани и неориентирани графи. 
+
+BFS използва структурата от данни опашка за да работи коректно. Самата идея е следната. Имаме начален връх, той ще бъде първия посетен. Добри кандидати да бъдат посетени след това са неговите съседи. Имаме функция adjacent (за ориентирани графи successors), та знаем кои са те. Добавяме ги в опашката, където чакат да бъдат посетени. След това последователно ги изваждаме от нея, и отново слагаме всички техни непосетени съседи в опашката, където чакат да бъдат посетени.
+
+Трябва ни обаче някакъв начин чрез който да разбираме дали даден връх е бил посетен. Ако нямаме тази информация зацикляме. С този проблем лесно се справяме правейки масив в който записваме дали даден връх е посетен или не.
+
+```
+BFS(G = (V, E), s начален връх) 
+    Създай опашка q и добави s вътре.
+    Създай булев масив visited[0..|V| - 1] със стойности false.
+
+    q.push(s).
+
+    while(!q.empty())
+        Нека cVertex е q.top().
+        q.pop().
+        Посети cVertex.
+        Добави в q всеки съсед на cVertex, който не е посетен.
+```
+
+Ако графът не е тегловен BFS може да се използва за намирането на най - къс път между два върха. Припомнете си задача втора от трети семинар и решението ѝ. Задача първа също използва идея, подобна на бфс.
+
+## DFS
+BFS обхожда графа ниво по ниво. DFS използва различна стратегия, наподобяваща обхождането на лабиринт. Вървим по път докато не "стигнем до края на този път" (нямаме накъде да отидем повече). След това се връщаме назад, докато не стигнем връх, който има непосетен съсед. Рекурсивно повтаряме тази стратегия върху непосетения съсед и внимаваме да не повторим връх два пъти.
+
+![](media/dfs-example.gif)
+
+DFS използва структурата от данни stack за да работи коректно. Важно е да се отбележи, че замяната на опашката със стек в DFS алгоритъма **не влече** кректен DFS. За наше улеснение ще направим функцията рекурсивна и ще използваме системния стек. 
+
+На примера виждаме едно DFS обхождане на граф. 
+
+Може да видите, че след като обхождането приключи, ребрата, които използваме да посетим връх за пръв път образуват дърво. Това до някаква степен е очаквано, DFS не повтаря върхове и открива всички върхове достижими от началния, тоест графа, който ще е обходен ще е свързан. 
+
+DFS посещава всеки връх и всяко ребро точно един път, което води до сложност O(|V| + |E|).
+
+DFS има много приложения, използва се за намиране на цикъл в граф, топологично сортиране на DAG (directet acyclic graph), търсене на пътища и др.
+
+Във файла DFS-Additional има интересни/допълнителни неща около DFS.
\ No newline at end of file
diff --git a/Seminar11/bfs-dfs.cpp b/Seminar11/bfs-dfs.cpp
index 19ef1b9..75a6f3d 100644
--- a/Seminar11/bfs-dfs.cpp
+++ b/Seminar11/bfs-dfs.cpp
@@ -49,9 +49,10 @@ void DFS(const AdjListGraph& g, AdjListGraph::vertex_t start) {
     DFSRec(visited, g, start);
 }
 
+
 int main() {
-    MatrixGraph g(5);
-    // AdjListGraph g(5);
+    // MatrixGraph g(5);
+    AdjListGraph g(5);
     g.addEdge(0, 2, 1);
     g.addEdge(0, 3, 1);
     g.addEdge(0, 1, 1);
@@ -60,5 +61,5 @@ int main() {
     g.addEdge(3, 4, 1);
     g.addEdge(1, 3, 1);
 
-    BFS(g, 0);
+    DFS(g, 0);
 }
\ No newline at end of file
diff --git a/Seminar11/media/dfs-example.gif b/Seminar11/media/dfs-example.gif
new file mode 100644
index 0000000..463d476
--- /dev/null
+++ b/Seminar11/media/dfs-example.gif
diff --git a/Seminar12/Dijkstra.cpp b/Seminar12/Dijkstra.cpp
new file mode 100644
index 0000000..3ce9de2
--- /dev/null
+++ b/Seminar12/Dijkstra.cpp
@@ -0,0 +1,97 @@
+#include"../Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.h"
+#include<queue>
+#include<iostream>
+#include<list>
+
+using vertex_t = MatrixGraph::vertex_t;
+using weight_t = MatrixGraph::weight_t;
+
+bool relax(std::vector<weight_t>& distance, const MatrixGraph& g, vertex_t reached, vertex_t currentVertex) {
+    if (distance[reached] > distance[currentVertex] + g.getWeight(currentVertex, reached)) {
+        distance[reached] = distance[currentVertex] + g.getWeight(currentVertex, reached);
+        return true;
+    }
+    return false;
+}
+
+// Намиране на най - къс път между два върха
+int Dijkstra(const MatrixGraph& g, vertex_t start, vertex_t end) {
+    std::vector<vertex_t> parent(g.vertexCount(), -1);
+    std::vector<weight_t> distances(g.vertexCount(), INT_MAX);
+
+    struct VertexDistancePair {
+        vertex_t vertex;
+        weight_t distanceFromStart;
+
+        bool operator<(const VertexDistancePair& other) const {
+            return distanceFromStart > other.distanceFromStart;
+        }
+    };
+
+    std::priority_queue<VertexDistancePair> q;
+
+    distances[start] = 0;
+    q.push({ start, 0 });
+
+    while (!q.empty()) {
+        auto currentPair = q.top();
+        q.pop();
+
+        if (currentPair.vertex == end) {
+            auto currentVertex = currentPair.vertex;
+
+            std::list<vertex_t> path;
+
+            while (currentVertex != start) {
+                path.insert(path.begin(), currentVertex);
+                currentVertex = parent[currentVertex];
+            }
+
+            path.insert(path.begin(), start);
+
+            for (const auto& v : path)
+                std::cout << v << std::endl;
+
+            return distances[currentPair.vertex];
+        }
+
+        const auto& adjacent = g.adjacent(currentPair.vertex);
+
+        for (auto reached : adjacent) {
+            if (relax(distances, g, reached, currentPair.vertex)) {
+                parent[reached] = currentPair.vertex;
+                q.push({ reached, distances[reached] });
+            }
+        }
+    }
+
+    return INT_MAX;
+}
+
+int main() {
+    MatrixGraph g(8);
+
+    g.addEdge(0, 1, 23);
+    g.addEdge(0, 2, 74);
+    g.addEdge(0, 3, 24);
+
+    g.addEdge(1, 2, 35);
+    g.addEdge(1, 4, 23);
+
+    g.addEdge(2, 4, 24);
+    g.addEdge(2, 3, 26);
+
+    g.addEdge(3, 6, 32);
+
+    g.addEdge(4, 5, 51);
+    g.addEdge(4, 7, 17);
+
+    g.addEdge(5, 7, 15);
+
+    g.addEdge(6, 7, 32);
+
+
+    int sp = Dijkstra(g, 0, 7);
+
+    std::cout << std::endl << sp;
+}
\ No newline at end of file
diff --git a/Seminar12/README.md b/Seminar12/README.md
new file mode 100644
index 0000000..2337958
--- /dev/null
+++ b/Seminar12/README.md
@@ -0,0 +1,142 @@
+# Най - къси пътища в граф.
+Обобщение: Разглеждаме накратко структурата от данни приоритетна опашка.
+
+## Приоритетни опашки, но накратко
+В първата част на курса се запознахме със структурата от данни опашка. В приоритетната опашка отново можем да вкарваме и изваждаме елементи, но този път не излиза най - рано добавения елемент. Всеки елемент има приоритет и когато извадим елемент излиза най - приоритетния. Примерно, ако елементите ни са цели числа, можем да кажем, че колкото по - малък е един елемент толкова по - малък приоритет има той.
+
+Такава приоритетна опашка се нарича min priority queue.
+
+```cpp
+#include<queue>
+#include<iostream>
+
+int main() {
+	// * int - от какъв тип са елементите
+	// * std::vector<int> - за да държи елементите тази опашка използва друг контейнер като ги нарежда хитро в него.
+	// този контейнер избираме да е std::vector<int>
+	// * std::less<int> - как определяме приоритета на елементите.
+	std::priority_queue<int, std::vector<int>, std::less<int>> q;
+
+	q.push(3);
+	q.push(2);
+	q.push(4);
+	q.push(1);
+
+	while (!q.empty()) {
+		// Излиза най - приоритетния елемент в началото 4 след това 3 и тн.
+		std::cout << q.top() << " ";
+		q.pop();
+	}
+}
+```
+
+Приоритетните опашки и начинът за тяхната реализация може да отнеме един цял семинар. Може да мислите за приоритетната опашка като за абстрактен тип от данни, който поддържа някакъв интерфейс, и за който имаме различни хитри начини да бъде реализиран.
+
+Изваждането на елемент от приоритетната опашка е със сложност O(log(n)) където n e броя на елементите в опашката. Също така можем да построим приоритетна опашка в O(n) време.
+
+## Алгоритъм на Dijkstra
+Алгоритъмът на Dijkstra намира най - къс път в ориентиран граф. **Алгоритъмът на Dijkstra не работи коректно, ако има отрицателни тегла, дори да няма отрицателни цикли!**
+
+Коректността на алгоритъма е сравнително трудна за доказване, затова ще разгледаме примерен код.
+
+```cpp
+bool relax(std::vector<weight_t>& distance, const MatrixGraph& g, vertex_t reached, vertex_t currentVertex) {
+    if (distance[reached] > distance[currentVertex] + g.getWeight(currentVertex, reached)) {
+        distance[reached] = distance[currentVertex] + g.getWeight(currentVertex, reached);
+        return true;
+    }
+    return false;
+}
+
+// Намиране на най - къс път между два върха
+int Dijkstra(const MatrixGraph& g, vertex_t start, vertex_t end) {
+    std::vector<vertex_t> parent(g.vertexCount(), -1);
+    std::vector<weight_t> distances(g.vertexCount(), INT_MAX);
+
+    struct VertexDistancePair {
+        vertex_t vertex;
+        weight_t distanceFromStart;
+
+        bool operator<(const VertexDistancePair& other) const {
+            return distanceFromStart > other.distanceFromStart;
+        }
+    };
+
+    std::priority_queue<VertexDistancePair> q;
+
+    distances[start] = 0;
+    q.push({ start, 0 });
+
+    while (!q.empty()) {
+        auto currentPair = q.top();
+        q.pop();
+
+        if (currentPair.vertex == end) {
+            auto currentVertex = currentPair.vertex;
+
+            std::list<vertex_t> path;
+
+            while (currentVertex != start) {
+                path.insert(path.begin(), currentVertex);
+                currentVertex = parent[currentVertex];
+            }
+
+            path.insert(path.begin(), start);
+
+            for (const auto& v : path)
+                std::cout << v << std::endl;
+
+            return distances[currentPair.vertex];
+        }
+
+        const auto& adjacent = g.adjacent(currentPair.vertex);
+
+        for (auto reached : adjacent) {
+            if (relax(distances, g, reached, currentPair.vertex)) {
+                parent[reached] = currentPair.vertex;
+                q.push({ reached, distances[reached] });
+            }
+        }
+    }
+
+    return INT_MAX;
+}
+```
+Функцията връща най - късия път между start и end. За да имаме този път ни трябва масив, в който ще пазим предшествениците. Този масив наричаме parent.
+
+Ако имаме път 1 3 7, то
+* parent[1] = -1
+* parent[3] = 1
+* parent[7] = 3
+
+Също така в масивът distances ще записваме локално колко е цената на най - късия път от старта, открит до момента.
+Нека v e връх. Сега знаем, че distances[v] e дължината на най - късия път, който сме намерили до момента. Тоест, има някакъв път s -> v.
+
+Нека u e наследник на v. Знаем, че в distances[u] rма дължината на най - късия път, който сме открили до момента. Има два начина да стигнем до u. Първият начин е s -> u (пътят, чиято стойност е записана във distances[u]. Забележете, че ако такъв път не е открит, фактът, че стойността е INT_MAX отново води до коректно изпълнение). Вторият начин е s -> v -> u. 
+
+Възможно ли е да сме намерили по - лек път от s -> u? Нека проверим. Тази проверка е отговорност на функцията relax:
+
+```
+relax(u, v):
+    if d[u] > d[v] + weight(v, u)   // Ако пътят s -> v -> u e по - лек от пътят d[u]
+        d[u] = d[v] + weight(v, u)  // Си открил нов най - лек път. Запиши го.
+```
+
+Създаваме приоритетна опашка в която ще държим наредени двойки от типа (връх, тегло на най - къс път).
+
+Всеки път от тази опашка ще вадим **върхът с най - лек път**. Затова съзваме структурата, представляваща двойка. В приоритетната опашка тя ще представлява приоритета на всеки връх. Оригиналния алгоритъм зарежда в приоритетната опашка веднага всички върхове и ъпдейтва ключовете им директно в опашката.
+
+Сега, докато има елементи в опашката вземаме най - лекия връх v. За всеки негов съсед u, ако можем да го релаксираме го добавяме в опашката с разстоянието, което сме намерили. 
+
+Когато върхът, който извадим от опашката е end в distances[end] e записан най - късия път от началото до end. Това твърдение също не е очевидно, но е вярно. 
+
+Та, когато извадим end от опашката ни остава само да възстановим пътя и да върнем неговата стойност. Извеждаме го на стандартния изход, понеже това е примерен код. След това връщаме и самата дължина. 
+
+Използваме std::list понеже добавянето в началото е бързо, но със същия успех бихме могли да добавяме в края на вектор примерно и да го обърнем след това. 
+
+Ако искаме най - късите пътища от s до всички достижими върхове, просто ще изчакаме алгоритъма да приключи. След това ще върнем distances и parent за да можем да възстановим пътя за всеки връх.
+
+## Сложност
+Ако търсим най - къси пътища в нетегловен граф няма нужда да използваме Dijkstra. Един прост bfs би ни свършил работа.
+
+Сложността на Dijkstra зависи от реализацията на приоритетната опашка, която използваме.
\ No newline at end of file