From 2ff0384a6e5e697f97d640c7195dcd52c310b42b Mon Sep 17 00:00:00 2001 From: Andrew Guschin Date: Sun, 4 Apr 2021 19:29:28 +0400 Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=B8=D0=BB=20=D0=B0?= =?UTF-8?q?=D0=BB=D0=B3=D0=BE=D1=80=D0=B8=D1=82=D0=BC=20=D0=94=D0=B5=D0=B9?= =?UTF-8?q?=D0=BA=D1=81=D1=82=D1=80=D1=8B=20=D0=B2=20=D0=B0=D0=BB=D0=B3?= =?UTF-8?q?=D0=BE=D1=80=D0=B8=D1=82=D0=BC=D0=B0=D1=85=20=D0=BD=D0=B0=20?= =?UTF-8?q?=D0=B3=D1=80=D0=B0=D1=84=D0=B0=D1=85?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- graphs-algo/Makefile | 23 +++++++ graphs-algo/task1.cpp | 169 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 192 insertions(+) create mode 100644 graphs-algo/Makefile create mode 100644 graphs-algo/task1.cpp (limited to 'graphs-algo') diff --git a/graphs-algo/Makefile b/graphs-algo/Makefile new file mode 100644 index 0000000..7cdaf2a --- /dev/null +++ b/graphs-algo/Makefile @@ -0,0 +1,23 @@ +CXX=g++ +CFLAGS=-g -Wall +COMPILE=$(CXX) $(CFLAGS) + +task1: + $(COMPILE) -o task.out task1.cpp +test1: task1 + @printf "4\n4\n1 2 1\n2 3 1\n3 4 1\n4 1 1\n4\n2" | ./task.out + @printf "Answer: \n" + @printf "4\n4\n1 2 1\n2 3 5\n3 4 1\n4 1 2\n2\n3" | ./task.out + @printf "Answer: \n" + +task2: + $(COMPILE) -o task.out task2.cpp +test2: task2 + @printf "" | ./task.out + @printf "Answer: \n" + +clean: + rm -f task.out *.zip + +archive: clean + zip archive.zip *.cpp *.h diff --git a/graphs-algo/task1.cpp b/graphs-algo/task1.cpp new file mode 100644 index 0000000..cd96c72 --- /dev/null +++ b/graphs-algo/task1.cpp @@ -0,0 +1,169 @@ +#include +#include +#include +#include + +using namespace std; + +typedef vector> graph; +const int INF = int(1e9); + +void print(graph g) +{ + for (int i = 0; i < int(g.size()); ++i) + { + cout << i + 1 << ": "; + for (int j = 0; j < int(g[i].size()) - 1; ++j) + cout << g[i][j] + 1 << ", "; + + if (g[i].size() > 0) + cout << g[i].back() + 1; + else + cout << "нет смежных вершин"; + + cout << ";" << endl; + } +} + +void print2D(graph g) +{ + int n = int(g.size()); + for (int i = 0; i < n; ++i) + { + for (int j = 0; j < n - 1; ++j) + cout << setw(5) << g[i][j] << ","; + cout << setw(5) << g[i][n - 1] << endl; + } +} + +// Написание данного алгоритма сильно упрощается, если использовать +// матрицу смежности, а не список смежности. +void init(graph *g, int n, int k) +{ + for (int i = 0; i < n; ++i) + { + auto v = new vector(n, k); + (*g)[i] = *v; + } +} + +// В данной функции вычисляются массивы предков для каждой из вершин. +// В результате получается матрица по которой можно восстановить +// кратчайший путь между любой парой вершин без дополнительных вычислений. +graph dijkstra(graph g, int n) +{ + graph d(n), u(n), p(n); + init(&d, n, INF); + init(&u, n, 0); + init(&p, n, -1); + + // s - начальная вершина + for (int s = 0; s < n; ++s) + { + d[s][s] = 0; + for (int _ = 0; _ < n; ++_) + { + int m = INF; + int v = -1; + for (int p = 0; p < n; ++p) + { + if (u[s][p] == 1 || d[s][p] == -1) continue; + if (d[s][p] < m) + { + m = d[s][p]; + v = p; + } + } + u[s][v] = 1; + + // Производим релаксации + for (int to = 0; to < n; ++to) + { + int len = g[v][to]; + // Релаксации производтяся только в соседние для v вершины. + if (len == -1) continue; + + int new_len = d[s][v] + len; + if (new_len < d[s][to]) + { + d[s][to] = new_len; + p[s][to] = v; + } + } + } + } + return p; +} + +vector backtrack(graph paths, int start, int end) +{ + vector path; + int cur = end; + while (cur != start) + { + path.push_back(cur); + cur = paths[start][cur]; + } + path.push_back(start); + reverse(path.begin(), path.end()); + return path; +} + +int main() +{ + cout << "Введите количество вершин: "; + int n; + cin >> n; + + cout << "Введите количество рёбер: "; + int k; + cin >> k; + + graph g(n); + init(&g, n, -1); + + cout << "o----------------------o" << endl; + cout << "| Нумерация вершин с 1 |" << endl; + cout << "o----------------------o" << endl; + + cout << "Введите рёбра (неориентированные, взвешенные):" << endl; + for (int i = 0; i < k; ++i) + { + int a, b, c; + cin >> a >> b >> c; + a--; + b--; + g[a][b] = c; + g[b][a] = c; + + g[a][a] = 0; + g[b][b] = 0; + } + + cout << "Введённый граф:" << endl; + print2D(g); + + graph paths = dijkstra(g, n); + + cout << "Введите начальную вершину: "; + int a; + cin >> a; + a--; + + cout << "Введите конечную вершину: "; + int b; + cin >> b; + b--; + + auto path = backtrack(paths, a, b); + if (path.size() > 0) + { + for (int i = 0; i < int(path.size()) - 1; ++i) + cout << path[i] + 1 << " -> "; + cout << path.back() + 1 << endl; + } + else + cout << "Путь не найден" << endl; + + return 0; +} -- cgit v1.2.3