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

@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, сравниваешь текущую длину с минимальной.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .

@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