Улучшение времени работы алгоритма

@Fury67 · Регистрация: 12.11.2017

Студворк — интернет-сервис помощи студентам

Здравствуйте. Программа находит длину кратчайшего пути из А в B для взвешенного неориентированного графа. Формат входных данных: количество вершин; количество путей; вершина А - вершина B - вес ребра. Не работает деструктор, подскажите, что не так. Как можно уменьшить занимаемую программой память? Так как сейчас она очень много памяти потребляет.
Пример входных данных :
3 2
0 1 0
1 2 2
0 1

Вывод:
2

C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
#include <iostream>
#include <vector>
#include <stack>
#include <deque>
 
#include <queue>
 
 
using namespace std;
 
 
class Graph
{
public:
    virtual ~Graph() {}
    virtual int VertexCount() const = 0;
    virtual void AddArc(int from, int to, int weight) = 0;
    virtual int HasArc(int from, int to) const = 0;
    //virtual void GetArc(int from, std::vector<int> a) = 0;
};
 
 
 
 
 
 
 
class MatrixGraph : public Graph {
 
public:
    MatrixGraph(int n);
 
    ~MatrixGraph();
 
    int VertexCount() const {
        return vertexNumber;
    }
    void GetPrev(int from, std::vector<int> &a);
    void AddArc(int from, int to, int weight);
    int HasArc(int from, int to) const;
    void GetArc(int from, std::vector<int> &a);
    int size() {
        return vertexNumber;
    }
 
private:
    int **graph;
    int vertexNumber;
};
 
 
 
 
 
 
MatrixGraph::MatrixGraph(int n) {
    graph = new int*[vertexNumber = n];
    for (int i = 0; i < n; i++) {
        graph[i] = new int[n];
        for (int j = 0; j < n; j++) {
            graph[i][j] = -1;
        }
    }
 
}
 
MatrixGraph::~MatrixGraph() {
    /*for (int i = vertexNumber - 1; i > -1; i--) {
        delete[] graph[i];
    }
    delete[] graph;*/
}
 
void  MatrixGraph::AddArc(int from, int to, int weight) {
    if (from < 0 || from >= vertexNumber || to < 0 || to >= vertexNumber) return;
    graph[from][to] = weight;
}
 
int MatrixGraph::HasArc(int from, int to) const {
    if (from < 0 || from >= vertexNumber || to < 0 || to >= vertexNumber) return 0;
    return graph[from][to];
}
 
void MatrixGraph::GetArc(int from, std::vector<int> &a) {
    a.clear();
    a.resize(vertexNumber);
    for (int i = 0; i < vertexNumber; i++) {
        if (graph[from][i] != -1) {
            a[i] = i;
        }
    }
}
 
void MatrixGraph::GetPrev(int from, std::vector<int> &a) {
    a.clear();
    a.resize(vertexNumber);
    for (int i = 0; i < vertexNumber; i++) {
        if (graph[i][from] == 1) {
            a[i] = i;
        }
    }
}
 
 
void Print(const Graph & g) {
    int n = g.VertexCount();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            std::cout << (g.HasArc(i, j) ? '1' : '0') << ' ';
        }
        std::cout << endl;
    }
}
 
 
void buildTree2(MatrixGraph LG, int st, int end) {
 
    std::vector<int> dlina;
    std::vector<int> koldlina;
    std::vector<int> ps_;
 
    koldlina.resize(LG.size());
    dlina.resize(LG.size());
    ps_.resize(LG.size());
 
    for (int i = 0; i < LG.size(); i++) {
        dlina[i] = 10001;
        koldlina[i] = 0;
        ps_[i] = -1;
    }
 
    koldlina[st] = 1;
    dlina[st] = 0;
    ps_[st] = -1;
 
    std::queue<int> q;
    q.push(st);
 
    while (!q.empty()) {
        std::vector<int> a;
        LG.GetArc(q.front(), a);
        for (int i = 0; i < a.size(); i++) {
            if (LG.HasArc(q.front(), a[i]) != -1) {
                if (dlina[a[i]] > dlina[q.front()] + LG.HasArc(q.front(), a[i])) {
                    dlina[a[i]] = dlina[q.front()] + LG.HasArc(q.front(), a[i]);
                    if (a[i] != end) {
                        q.push(a[i]);
                        ps_[a[i]] == 0;
                    }
                }
            }
        }
        q.pop();
    }
 
 
    if (dlina[end] == 10001) {
        std::cout << "0";
    }
    else {
        std::cout << dlina[end];
    }
}
 
 
 
 
 
 
 
 
 
 
int main()
{
 
    int N, M;
    std::cin >> M >> N;
 
    MatrixGraph LG(M);
    int k, l;
    int w;
    for (int i = 0; i < N; i++) {
        std::cin >> k >> l >> w;
        if (LG.HasArc(k, l) == -1) {
            LG.AddArc(k, l, w);
            LG.AddArc(l, k, w);
        } 
        else {
            if (w < LG.HasArc(k, l)) {
                LG.AddArc(k, l, w);
                LG.AddArc(l, k, w);
            }
        }
    }
    
 
    int st, end;
    std::cin >> st >> end;
    if (N != 0, M != 0) {
        buildTree2(LG, st, end);
    }
    else {
        std::cout << "0";
    }
 
 
}

@lemegeton · 12.11.2019, 23:46

Сообщение от Fury67

/*for (int i = vertexNumber - 1; i > -1; i--) {
delete[] graph[i];
}
delete[] graph;*/

Да вроде похоже на правду. Как проявляется это "не работает"?

C++
1
2
3
4
for (int i = 0; i < vertexNumber; ++i) {
     delete[] graph[i];
}
delete [] graph;

Сообщение от Fury67

MatrixGraph::MatrixGraph(int n) {
graph = new int*[vertexNumber = n];
for (int i = 0; i < n; i++) {
graph[i] = new int[n];
for (int j = 0; j < n; j++) {
graph[i][j] = -1;
}
}
}

Ваш граф неориентирован. Поэтому достаточно хранить половину матрицы. Вторая половина зеркальна. graph[i][j] == graph[j][i].

@Fury67 · 13.11.2019, 00:09 **[ТС]**

Попробуйте запустить программу с деструктором (я и вашим способом изначально пробывал). Она выведет недоработанное исключение в нем. Как хранить половину массива? Я же все равно выделаю память на целый массив. У меня потери памяти огромные, необходимо уместиться в 20Mb на определенном тесте, а у меня улетает за 150Mb... Я боюсь, что это связано с тем, как я храню граф. Ибо массив требует слишком много памяти. Сильно ли поможет использование вектора?

@lemegeton · 13.11.2019, 00:57

Зачем вы вообще так сложно это пишете? Все, что вам нужно, это сделать симметричную матрицу смежности и алгоритмом дийкстры найти длины кратчайших путей.

Например так:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <random>
#include <string>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <fstream>
#include <istream>
#include <istream>
#include <vector>
#include <map>
#include <unordered_map>
 
// симметричная матрица смежности
class SymmetricAdjacencyMatrix {
public:
    explicit SymmetricAdjacencyMatrix(std::size_t size) : size(size), data(new int*[size]) {
        for (std::size_t i = 0; i < size; ++i) {
            data[i] = new int[i + 1];
            std::fill_n(data[i], i + 1, -1);
        }
    }
    virtual ~SymmetricAdjacencyMatrix() {
        for (std::size_t i = 0; i < size; ++i) {
            delete[] data[i];
        }
        delete[] data;
    }
    int getSize() const { return size; }
    const int &operator()(std::size_t i, std::size_t j) const {
        return (i >= j) ? data[i][j] : data[j][i];
    }
    int &operator()(std::size_t i, std::size_t j) {
        return (i >= j) ? data[i][j] : data[j][i];
    }
private:
    SymmetricAdjacencyMatrix(const SymmetricAdjacencyMatrix &o);
    SymmetricAdjacencyMatrix &operator=(const SymmetricAdjacencyMatrix &o);
    std::size_t size;
    int** data;
};
 
std::ostream &operator<<(std::ostream& out, const SymmetricAdjacencyMatrix &g) {
    for (int i = 0; i < g.getSize(); ++i) {
        for (int j = 0; j < g.getSize(); ++j) {
            out << "\t" << g(i, j);
        }
        out << std::endl;
    }
    return out;
}
 
int main(int argc, char **argv) {
    SymmetricAdjacencyMatrix g(3);
 
    for (int i = 0; i < g.getSize(); ++i) {
        g(i, i) = 0;
    }
 
    g(0, 1) = 1;
    g(1, 2) = 2;
    g(0, 2) = 4;
 
    std::cout << g;
 
    // алгоритм Дийкстры нахождения кратчайшего пути ото всех до всех
    for (int k = 0; k < g.getSize(); ++k) {
        for (int i = 0; i < g.getSize(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (g(i, k) + g(k, j) < g(i, j)) {
                    g(i, j) = g(i, k) + g(k, j);
                }
            }
        }
    }
 
    // теперь g(i, j) хранит длину кратчайшего пути из точки i в точку j
    std::cout << g;
 
    return 0;
}

Добавлено через 3 минуты
Можно вообще без класса обойтись. Оно тут так... для удобства.

@XLAT · 13.11.2019, 00:57

Fury67,

Сообщение от Fury67

необходимо уместиться в 20Mb на определенном тесте, а у меня улетает за 150Mb

я так понял ваш алгоритм строит матрицу инцидентности
это кол-во узлов * количество ребер как минимум.
т.е. в худшем варианте ваши 20м могут вырасти в 400м.

вот была тема, где я делал поиск кратчайшего пути(алгоритм) без сей матрицы.
гляньте мож пригодиться:
Поиск пути среди двух чисел (по шагам)

@Fury67 · 13.11.2019, 20:51 **[ТС]**

XLAT, я попробовал ваш алгоритм, он меня не заработал (а разбираться что-то муторно).
lemegeton, спасибо за идею с работой только через половину матрицы смежности, но это вообще никак мне не поможет с проблемами в памяти. + алгоритм Флойда, который вы использовали для построения матрицы с длинами минимальных путей, слишком медленный.

Добавлено через 16 минут
Вообщем реализовал я так, память, вроде, вообще нигде не теряется. Но теперь проблема, в том, что на каком-то тесте она выдается неправильный ответ. Уже несколько часов бьюсь и не могу придумать такой тест. Буду признателен за помощь в поиске ошибки в данном алгоритме. Формат ввода аналогичен тому, что в первом сообщении темы.

C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
#include <vector>
#include <set>
#include <list>
 
 
 
 
class IGraph
{
public:
    virtual ~IGraph() {}
    virtual int size() const = 0;
    virtual void AddArc(int from, int to, int weight) = 0;
    virtual void GetArc(int vertex, std::vector<std::pair<int, int>> &vertices) const = 0;
};
 
class Graph : public IGraph {
public:
    Graph(int n);
    ~Graph() {};
 
    void AddArc(int from, int to, int weight);
    void GetArc(int vertex, std::vector<std::pair<int, int>> &vertices) const;
 
    int size() const {
        return vertexNumber;
    }
 
private:
    int vertexNumber;
    std::vector<std::list<std::pair<int, int>>> graph;
};
 
 
Graph::Graph(int size) : vertexNumber(size), graph(vertexNumber, std::list<std::pair<int, int>>()) {}
 
 
void Graph::AddArc(int from, int to, int weight)
{
    graph[from].push_back(std::make_pair(to, weight));
    graph[to].push_back(std::make_pair(from, weight));
}
 
 
void Graph::GetArc(int vertex, std::vector<std::pair<int, int>> &vertices) const
{
    vertices.clear();
    for (const std::pair<int, int> &i : graph[vertex]) {
        vertices.push_back(i);
    }
}
 
 
void build1(Graph const &graph, int from, int to) {
    std::vector<bool> used(graph.size(), false);
    std::vector<int> dlina(graph.size(), 10001);
    dlina[from] = 0;
    std::set<std::pair<int, int>> queue;
    queue.emplace(std::make_pair(0, from));
 
    while (!queue.empty()) {
        int v = (queue.begin())->second;
        queue.erase(queue.begin());
        used[v] = true;
 
        std::vector<std::pair<int, int>> a;
        graph.GetArc(v, a);
 
        for (std::pair<int, int> c : a) {
            if (dlina[c.first] > dlina[v] + c.second) {
                if (dlina[c.first] != 10001)
                    queue.erase(std::make_pair(dlina[c.first], c.first));
                dlina[c.first] = dlina[v] + c.second;
                queue.emplace(std::pair<int, int>(dlina[c.first], c.first));
            }
        }
    }
 
    if (dlina[to] != 10001) {
        std::cout << dlina[to];
    }
    else {
        std::cout << "0";
    }
}
 
 
int main() {
    int N, M, k, l, w;
    std::cin >> N >> M;
    if (N != 0 && M != 0) {
        Graph graph(N);
        for (int i = 0; i < M; i++) {
            std::cin >> k >> l >> w;
            graph.AddArc(k, l, w);
        }
        int from, to;
        std::cin >> from >> to;
 
        build1(graph, from, to);
    }
    else {
        std::cout << "0";
    }
    return 0;
}

@Fury67 · 15.11.2019, 10:44 **[ТС]**

Up the topic.

@oleg-m1973 · 15.11.2019, 11:06

Сообщение от Fury67

std::vector<std::list<std:

air<int, int>>> graph;

Сообщение от Fury67

Вообщем реализовал я так, память, вроде, вообще нигде не теряется. Но теперь проблема, в том, что на каком-то тесте она выдается неправильный ответ. Уже несколько часов бьюсь и не могу придумать такой тест. Буду признателен за помощь в поиске ошибки в данном алгоритме. Формат ввода аналогичен тому, что в первом сообщении темы.

Сообщение от Fury67

void Graph::GetArc(int vertex, std::vector<std:

air<int, int>> &vertices) const
{
vertices.clear();
for (const std:

air<int, int> &i : graph[vertex]) {
vertices.push_back(i);
}
}

Сообщение от Fury67

std::vector<std:

air<int, int>> a;
graph.GetArc(v, a);
for (std:

air<int, int> c : a) {

Зачем ты здесь копируешь массив, который не изменяется?
Сделай

C++
1
2
3
4
5
6
7
8
9
cont std::list<std::pair<int, int>> &GetArc(int vertex, const
{
return graph[vertex];
}
....................
 
//        std::vector<std::pair<int, int>> a;
//        graph.GetArc(v, a);
for (std::pair<int, int> c : graph.GetArc(v)) {;

@Fury67 · 15.11.2019, 11:23 **[ТС]**

oleg-m1973, на время работы это повлияет, спасибо. Но сейчас проблема в том, что сам алгоритм валиться в определённых случаях. Я пока что не смог придумать такие случаи. Может у вас получится?

@oleg-m1973 · 15.11.2019, 11:45

Сообщение от Fury67

oleg-m1973, на время работы это повлияет, спасибо. Но сейчас проблема в том, что сам алгоритм валиться в определённых случаях. Я пока что не смог придумать такие случаи. Может у вас получится?

По-моему, массив dlina здесь совершенно не нужен, а вместо queue нужно использовать рекурсию.
Т.е. сам путь тебе здесь хранить не нужно, достаточно вычислять длину пути.
Рекурсивно пробегаешься по всем узлам, при входе в рекурсию - прибавляешь длину, при выходе уменьшаешь.
Выход из рекурсии - если used[v] == true, или v == to
Если достиг вершины to, сравниваешь текущую длину с минимальной.

Новые блоги и статьи Все статьи Все блоги /
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Рецензия / Мнение/ Перевод https:/ / **********/ gallery/ thinkpad-x220-tablet-porn-gzoEAjs . . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .

@Fury67 Заяц, просто Заяц. 666 / 280 / 156 Регистрация: 12.11.2017 Сообщений: 882
	13.11.2019, 00:09 [ТС]
	Попробуйте запустить программу с деструктором (я и вашим способом изначально пробывал). Она выведет недоработанное исключение в нем. Как хранить половину массива? Я же все равно выделаю память на целый массив. У меня потери памяти огромные, необходимо уместиться в 20Mb на определенном тесте, а у меня улетает за 150Mb... Я боюсь, что это связано с тем, как я храню граф. Ибо массив требует слишком много памяти. Сильно ли поможет использование вектора? 0

@Fury67 Заяц, просто Заяц. 666 / 280 / 156 Регистрация: 12.11.2017 Сообщений: 882
	15.11.2019, 10:44 [ТС]
	Up the topic. 0

@Fury67 Заяц, просто Заяц. 666 / 280 / 156 Регистрация: 12.11.2017 Сообщений: 882
	15.11.2019, 11:23 [ТС]
	oleg-m1973, на время работы это повлияет, спасибо. Но сейчас проблема в том, что сам алгоритм валиться в определённых случаях. Я пока что не смог придумать такие случаи. Может у вас получится? 0