Website Summary Files Commits Branches @commit @diff @stats
path: root / Seminar12
diff options
context:
space:
mode:
Commit63f4cb943f81c257e78ebeef828edbc04e78264b (patch)
Author
 Stoycho Kyosev <stoycho.kk@gmail.com>
2023-01-04 15:07:15 +0200
Committer
 Stoycho Kyosev <stoycho.kk@gmail.com>
2023-01-04 15:07:15 +0200
Files2a9972460ab6719f392f56f84f1edc2f568b85b8 /Seminar12
Data-structures-and-algorithms-63f4cb943f81c257e78ebeef828edbc04e78264b.tar
Data-structures-and-algorithms-63f4cb943f81c257e78ebeef828edbc04e78264b.tar.gz
Data-structures-and-algorithms-63f4cb943f81c257e78ebeef828edbc04e78264b.zip
Parentfcb06959d4425310eadee643f3fab68604063f51 (diff)
Add seminar 12
2 files changed, 239 insertions, 0 deletions
-rw-r--r--Seminar12/Dijkstra.cpp97
-rw-r--r--Seminar12/README.md142
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