diff options
Add seminar 12
2 files changed, 239 insertions, 0 deletions
| -rw-r--r-- | Seminar12/Dijkstra.cpp | 97 | ||||
| -rw-r--r-- | Seminar12/README.md | 142 |
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 |
