Добавил алгоритм Дейкстры в алгоритмах на графах

2 files changed, 192 insertions, 0 deletions

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<iostream>
+#include<vector>
+#include<algorithm>
+#include<iomanip>
+
+using namespace std;
+
+typedef vector<vector<int>> 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<int>(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<int> backtrack(graph paths, int start, int end)
+{
+    vector<int> 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;
+}