Website Summary Files Commits Branches @commit @diff @stats
path: root / Seminar12
diff options
context:
space:
mode:
Commit7eee5a78005a9a569186d2c8b4b645a818ab9bf1 (patch)
Author
 Stoycho Kyosev <skyosev@192.168.100.17>
2024-10-06 07:04:44 -0400
Committer
 Stoycho Kyosev <skyosev@192.168.100.17>
2024-10-06 07:04:44 -0400
Files84594e0af29cefa5aae76ace5f8eb81484400e31 /Seminar12
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.tar
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.tar.gz
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.zip
Parent0841635826cb03c0e74cd75ec3c97c4c3b594d8b (diff)
Cleanup
2 files changed, 0 insertions, 243 deletions
-rw-r--r--Seminar12/Dijkstra.cpp97
-rw-r--r--Seminar12/README.md146
diff --git a/Seminar12/Dijkstra.cpp b/Seminar12/Dijkstra.cpp
deleted file mode 100644
index 3ce9de2..0000000
--- a/Seminar12/Dijkstra.cpp
+++ /dev/null
@@ -1,97 +0,0 @@
-#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
deleted file mode 100644
index 8696283..0000000
--- a/Seminar12/README.md
+++ /dev/null
@@ -1,146 +0,0 @@
-# Най - къси пътища в граф.
-Обобщение: Разглеждаме накратко структурата от данни приоритетна опашка. Разглеждаме алгоритъма на Dijkstra и функцията relax.
-
-## Приоритетни опашки, но накратко
-В първата част на курса се запознахме със структурата от данни опашка. В приоритетната опашка отново можем да вкарваме и изваждаме елементи, но този път не излиза най - рано добавения елемент. Всеки елемент има приоритет и когато извадим елемент излиза най - приоритетния. Примерно, ако елементите ни са цели числа, можем да кажем, че колкото по - малък е един елемент толкова по - малък приоритет има той.
-
-Такава приоритетна опашка се нарича 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) време.
-
-Приоритетните опашки често имат операцията decrease-key. Ако приоритетната опашка е от двойки ключ и стойност искаме да намалим ключа на дадена стойност. Тази операция е O(log(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) // Си открил нов най - лек път. Запиши го.
-```
-
-Създаваме приоритетна опашка в която ще държим наредени двойки от типа (връх, тегло на най - къс път).
-
-Всеки път от тази опашка ще вадим **върхът с най - лек път**. Затова съзваме структурата, представляваща двойка. В приоритетната опашка пътят от старта до върха ще представлява приоритета на върха. Оригиналният алгоритъм зарежда в приоритетната опашка веднага всички върхове и ъпдейтва ключовете им директно в опашката чрез функцията decrease-key. В началото всички ключове без началния са INT_MAX и след това постепенно се прилага decrease key всеки път когато открием по - кратък път. Тук приемаме друг подход, постепенно добавяме върхове в опашката, понеже std::priority_queue не поддържа decrease key. Това ще доведе до добавяне на върха няколко пъти в опашката но с различни ключове (всеки път когато намерим по - къс път). Това обаче не прави алгоритъма некоректен, просто върти малко повече.
-
-Сега, докато има елементи в опашката вземаме най - лекия връх v (този с минимален ключ т.е. с най - малък открит път от старта до него). За всеки негов съсед u, ако можем да го релаксираме го добавяме в опашката с разстоянието, което сме намерили.
-
-Когато върхът, който извадим от опашката е end в distances[end] e записан най - късия път от началото до end. Това твърдение също не е очевидно, но е вярно.
-
-Та, когато извадим end от опашката ни остава само да възстановим пътя и да върнем неговата стойност. Извеждаме го на стандартния изход, понеже това е примерен код. След това връщаме и самата дължина.
-
-Използваме std::list понеже добавянето в началото е бързо, но със същия успех бихме могли да добавяме в края на вектор примерно и да го обърнем след това.
-
-Ако искаме най - късите пътища от s до всички достижими върхове, просто ще изчакаме алгоритъма да приключи. След това ще върнем distances и parent за да можем да възстановим пътя за всеки връх.
-
-Сложността на представената версия на Dijkstra е O(|E|log(|E|)). Сложността на оригиналната Dijkstra реализирана с binary heap е
-O(|V|log|V| + |E|log|V|)
-* |V|*log(|V|) - в началото добавяме |V| елемента в приоритетната опашка. Всяко добавяне е log(|V|) време
-* |E|log|V| - Можем да имаме |E| операции decrease key (ако релаксираме за всяко ребро). Всеки decrease-key е log|V|.
-
-С изтънчени структури от данни Dijkstra може да стане и по - бърз **асимптотично**. \ No newline at end of file