Форум программистов, компьютерный форум CyberForum.ru

Алгоритм Дейкстры - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Где найти следующую ступень знаний по С++? http://www.cyberforum.ru/cpp-beginners/thread855410.html
Дело в том, что я уже давно заинтересован изучением C++, не понимаю почему, но именно к нему тянет :). Ладно дело не в том куда я держу свой путь, а в том что я не могу продолжить сдвиг с этого места. я долгое время ищу новых знаний, но всё не в том направлении... Я уже безошибочно могу писать задачки такого типа без шпаргалок и т.д. Я не хочу останавливаться на этом и желаю продолжать...
C++ Кодирование файла Задача написать часть полиморфного вируса для курсовой. Т.е нужно подать нашей программе на вход файл она должна зашифровать его по случайному ключу расшифровать и исполнить. 1 Вопрос как можно зашифровать? 2 Как его исполнить? http://www.cyberforum.ru/cpp-beginners/thread855399.html
Двоичное дерево Хаффмана C++
Дана некоторая последовательность данных...(то есть набор каких то значений)...этот набор представляет из себя набор конечных потомков двоичного дерева....например если набор из двух элементов то всего 1 уровень у дерева если набор из 4 элементов то два уровня ...собственно вопрос в том как программно реализовать построение дерева на основе конечных потомков...(нужно для метода кодирования...
Эйлеровы циклы C++
Ребят, помогите с задачкой. на входе есть ориентированный граф, который задается файликом вида n m v1 u1 v2 u2 ... vm um где n - кол-во вершин графа, m - кол-во ребер, v - начальная вершина ребра, u конечная, можно сказать что граф задается списком ребер. Нужно: найти Эйлеровы циклы в графе и вывести их на экран, если нету циклов тогда найти Эйлеровы маршруты в графе.
C++ расстояние от окружности к ломаной? http://www.cyberforum.ru/cpp-beginners/thread855370.html
написать функцию: даны координаты 20 точек ломаной, найти три круга, которые находятся дальше от нее и три ближайших окружности. есть координаты центров окружностей и их радиус, количество кругов неопределенная, но больше 7. ломаная задана объектами класса линия окружности являются объектами класса окружность это все условие, поэтому алгоритм поиска не определен
C++ Дана сторка содержащая полное имя файла Дана строка содержащая полное имя файла. выделить из этой строки имя последнего каталога. если файл содержится в корневом каталоге то вывести первую букву каталога подробнее

Показать сообщение отдельно
__General__
24 / 24 / 3
Регистрация: 04.01.2014
Сообщений: 91
Завершенные тесты: 2
03.05.2014, 03:49     Алгоритм Дейкстры
В числе прочих функций здесь есть реализация алгоритма Дейкстры

хедр:
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
82
83
84
85
86
87
88
89
#ifndef GRAPH_H
#define GRAPH_H
 
#include <string>
#include <iostream>
#include <fstream>
#include <algorithm>
 
#include "Queue.h"
#include "Prior_Queue.h"
 
using namespace std;
 
class edge;
class vertex;
class graph;
 
class edge
{
public:
    int price;  //цена ребра.
    edge *next_edge;    //указатель на след. ребро в списке. 
    vertex *neighbour;  //указатель на соседнюю вершину. 
 
    edge(int);
    ~edge();
};
 
class vertex
{
public:
    string name;
 
    bool was_in_queue; //была ли вершина в очереди.
    int priority;    //приоритет в очереди.
 
    int dist; //используется при вычислении эксцентриситета -- расстояние между этой вершиной и вершиной, эксцентриситет которой мы вычисляем.
    int eccent;  //эксцентриситет вершины.
 
    edge *edge_list;
    vertex *next_vert;
    vertex *pred_vert ; //указатель на предыдущую вершину в пути
 
    vertex(string);
    ~vertex();
 
    bool is_neighb(vertex*); //определяет, есть ли ребро между данными вершинами.
    int get_prior(vertex*);  //вычисляет приоритет вершины, зная приоритет вершины-соседа-источника (для приоритетной очереди). 
};
 
class Graph
{
public:
    Graph();
    ~Graph();
 
    bool add_edge(string, string, int);
    bool del_edge(string, string);
    bool add_vert(string);
    bool del_vert(string);
 
    void print_console();
    void read_from_file (ifstream&);
    void print_file(ofstream&, string, string);
    void print_file_ecc(ofstream&);
 
    bool best_way_search(string, string);  //поиск кратчайшего пути.
    void print_way(string, string);        //распечатка пути.
    void pred_search();                    //обнуление указателей pred.
 
    void prepare_draw();  //вычисление эксцентриситетов, сортировка вершин графа по эксцентриситетам.
 
private:
    int num_vert;
    int num_edge;
 
    vertex *vert_list;
 
    vertex* SearchByName(string);
    void SortByEccent();  //сортировка вершин по возрастанию эксцентриситетов.
 
    void add_edge(vertex*, vertex*, int);
    void del_edge(vertex*, vertex*);
    void del_vert(vertex*);
 
    void get_eccent(vertex*);
};
 
#endif

cpp-файл:
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
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
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
#include "Graph.h"
 
edge::edge(int _price)
{
    price = _price;
    next_edge = nullptr;
    neighbour = nullptr;
}
 
edge::~edge()
{
}
 
 
vertex::vertex(string _name)
{
    name = _name;
    
    was_in_queue = false;
    priority = 0;
 
    dist = 0;
    eccent = 0;
 
    edge_list = new edge(0);
    next_vert = nullptr;
    pred_vert = nullptr;
}
 
vertex::~vertex()
{
}
 
bool vertex::is_neighb(vertex *_vert) 
{
    edge *cur_e = edge_list->next_edge;
    while (cur_e) {
        if (cur_e->neighbour == _vert) {
            return true;
        }
        cur_e = cur_e->next_edge;
    }
    return false;
}
 
int vertex::get_prior(vertex *pr_vert)
{
    if (pr_vert) {
        edge *cur_e = edge_list->next_edge;
        while (cur_e->neighbour != pr_vert) {
            cur_e = cur_e->next_edge;
        }
        return pr_vert->priority+cur_e->price;
    }
    else {
        return 0;
    }
}
 
 
Graph::Graph()
{
    vert_list = new vertex("");
 
    num_vert = 0;
    num_edge = 0;
}
 
Graph::~Graph()
{
    while (vert_list->next_vert) {
        del_vert(vert_list->next_vert);
    }
    
    delete vert_list;
}
 
void Graph::add_edge(vertex *vert_1, vertex *vert_2, int _price)
{
    edge *add_e1 = new edge(_price);
    add_e1->neighbour = vert_2;
    add_e1->next_edge = vert_1->edge_list->next_edge;
    vert_1->edge_list->next_edge = add_e1;
 
    edge *add_e2 = new edge(_price);
    add_e2->neighbour = vert_1;
    add_e2->next_edge = vert_2->edge_list->next_edge;
    vert_2->edge_list->next_edge = add_e2;
 
    num_edge++;
}
 
bool Graph::add_edge(string name_v1, string name_v2, int _price)
{
    vertex *v1 = SearchByName(name_v1);
    vertex *v2 = SearchByName(name_v2);
 
    if (v1 && v2) {
        add_edge(v1, v2, _price);
        return true;
    }
    else {
        return false;
    }
}
 
void Graph::del_edge(vertex *vert_1, vertex *vert_2)
{
    edge *cur_e = vert_1->edge_list->next_edge, *prev_e = vert_1->edge_list;
    while (cur_e->neighbour != vert_2) {
        prev_e = cur_e;
        cur_e = cur_e->next_edge;
    }
    prev_e->next_edge = cur_e->next_edge;
    delete cur_e;
 
    cur_e = vert_2->edge_list->next_edge, prev_e = vert_2->edge_list;
    while (cur_e->neighbour != vert_1) {
        prev_e = cur_e;
        cur_e = cur_e->next_edge;
    }
    prev_e->next_edge = cur_e->next_edge;
    delete cur_e;
 
    num_edge--;
}
 
bool Graph::del_edge(string name_v1, string name_v2)
{
    vertex *v1 = SearchByName(name_v1);
    vertex *v2 = SearchByName(name_v2);
 
    if (v1 && v2) {
        del_edge(v1, v2);
        return true;
    }
    else {
        return false;
    }
}
 
bool Graph::add_vert(string _name)
{
    if (!SearchByName(_name)) {
        vertex *add_v = new vertex(_name);
        add_v->next_vert = vert_list->next_vert;
        vert_list->next_vert = add_v;
 
        num_vert++;
        return true;
    }
    else {
        return false;
    }
}
 
void Graph::del_vert(vertex *del_v)
{
    edge *del_e = del_v->edge_list->next_edge, *cur_e;
    while (del_e) {
        cur_e = del_e->next_edge;
        del_edge(del_v, del_e->neighbour);
        del_e = cur_e;
    }
 
    vertex *prev_v = vert_list;
    while (prev_v->next_vert != del_v) {
        prev_v = prev_v->next_vert;
    }
    prev_v->next_vert = del_v->next_vert;
    delete del_v;
 
    num_vert--;
}
 
bool Graph::del_vert(string name)
{
    vertex *del_v = SearchByName(name);
    if (del_v) {
        del_vert(del_v);
        return true;
    }
    else {
        return false;
    }
}
 
 
vertex* Graph::SearchByName(string _name)
{
    vertex *seek_v = vert_list->next_vert;
    while (seek_v && seek_v->name != _name) {
        seek_v = seek_v->next_vert;
    }
    return seek_v;
}
 
void Graph::SortByEccent()//пузырек.
{
    vertex *prev_v, *cur_v, *next_v;
    int i;
    for (i = 0; i < num_vert; i++) {
        prev_v = vert_list;
        cur_v = vert_list->next_vert;
        next_v = vert_list->next_vert->next_vert;
        while (next_v) {
            if (cur_v->eccent > next_v->eccent) {
                prev_v->next_vert = next_v;
                cur_v->next_vert = next_v->next_vert;
                next_v->next_vert = cur_v;
                prev_v = next_v;
            }
            else {
                prev_v = cur_v;
                cur_v = next_v;
            }
            next_v = cur_v->next_vert;
        }
    }
}
 
 
void Graph::print_console() 
{
    vertex *cur_v = vert_list->next_vert;
    edge *cur_e;
    cout <<'\n';
    while (cur_v) {
        cout <<cur_v->name <<": ";
        cur_e = cur_v->edge_list->next_edge;
        while (cur_e) {
            cout <<cur_v->name <<"-" <<cur_e->neighbour->name <<"(" <<cur_e->price <<")" <<"; ";
            cur_e = cur_e->next_edge;
        }
        cout <<'\n';
        cur_v = cur_v->next_vert;
    }
    cout <<'\n';
}
 
void Graph::read_from_file(ifstream &inp_g)
{
    int num_vert, num_edge, cur_price;
    inp_g >>num_vert >>num_edge;
 
    string cur_v_name_1, cur_v_name_2;
 
    int i;
    for (i = 0; i < num_vert; i++) {
        inp_g >>cur_v_name_1;
        add_vert(cur_v_name_1);
    }
    for (i = 0; i < num_edge; i++) {
        inp_g >>cur_v_name_1 >>cur_v_name_2 >>cur_price;
        add_edge(cur_v_name_1, cur_v_name_2, cur_price);
    }
    inp_g.close();
}
 
void Graph::print_file(ofstream &outp_g, string src_name, string tgt_name)
{
    outp_g <<num_vert <<" " <<num_edge <<'\n';
    
    vertex *cur_vert = vert_list->next_vert;
    while (cur_vert) {  //печатаем вершины.
        outp_g <<cur_vert->name <<" ";
        cur_vert = cur_vert->next_vert;
    }
    outp_g <<'\n';
    
    cur_vert = vert_list->next_vert;
    edge *cur_edge; 
    while (cur_vert) {  //печатаем ребра.
        cur_edge = cur_vert->edge_list->next_edge;
        while (cur_edge) {
            outp_g <<cur_vert->name <<" "<<cur_edge->neighbour->name <<" " <<cur_edge->price <<'\n';
            cur_edge = cur_edge->next_edge;
        }
        cur_vert = cur_vert->next_vert;
    }
 
    vertex *src = SearchByName(src_name);
    vertex *tgt = SearchByName(tgt_name);
    cur_vert = tgt;
    while (cur_vert) {
        outp_g <<cur_vert->name <<" ";
        cur_vert = cur_vert->pred_vert;
    }
    outp_g <<'\n';
}
 
void Graph::print_file_ecc(ofstream &outp_g)
{
    outp_g <<num_vert <<" " <<num_edge <<'\n';
    
    vertex *cur_vert = vert_list->next_vert;
    while (cur_vert) {  //печатаем вершины.
        outp_g <<cur_vert->name <<" "<<cur_vert->eccent <<'\n';
        cur_vert = cur_vert->next_vert;
    }
    
    cur_vert = vert_list->next_vert;
    edge *cur_edge; 
    while (cur_vert) {  //печатаем ребра.
        cur_edge = cur_vert->edge_list->next_edge;
        while (cur_edge) {
            outp_g <<cur_vert->name <<" "<<cur_edge->neighbour->name <<" " <<cur_edge->price <<'\n';
            cur_edge = cur_edge->next_edge;
        }
        cur_vert = cur_vert->next_vert;
    }
}
 
 
bool Graph::best_way_search(string SourceName, string TargetName)
{
    vertex *source = SearchByName (SourceName), *target = SearchByName (TargetName);
 
    Prior_Queue Q;
 
    Q.enqueue_vert(source, nullptr);  //добавляем источник в очередь.
    vertex *deq_v;
    edge *cur_e;
    int cur_prior = 0;
    while (!Q.is_empty()) {  //пока очередь не пуста.
        deq_v = Q.dequeue_vert();
        if (deq_v == target) {
            Q.clear();
            return true;
        }
        cur_e = deq_v->edge_list->next_edge;
        while (cur_e) {
            if (cur_e->neighbour != deq_v->pred_vert) {
                if (!cur_e->neighbour->pred_vert) {  //если мы встретили вершину впервые.
                    cur_e->neighbour->pred_vert = deq_v;
                    Q.enqueue_vert(cur_e->neighbour, cur_e->neighbour->pred_vert);
                }
                else {
                    cur_prior = cur_e->neighbour->get_prior(deq_v);
                    if (cur_prior < cur_e->neighbour->priority) {
                        cur_e->neighbour->priority = cur_prior;
                        cur_e->neighbour->pred_vert = deq_v;
                        if (!Q.search_vert(cur_e->neighbour)) {
                            Q.enqueue_vert(cur_e->neighbour, cur_e->neighbour->pred_vert);
                        }
                    }
                }
            }
            cur_e = cur_e->next_edge;
        }
    }
 
    return false;
}
 
void Graph::print_way(string Source_Name, string Target_Name)
{
    vertex *src = SearchByName(Source_Name), *tgt = SearchByName(Target_Name);
 
    cout <<'\n' <<"Оптимальный путь: ";
    vertex *print_v = tgt;
    while (print_v != src) {
        cout <<print_v->name <<" <- ";
        print_v = print_v->pred_vert;
    }
    cout <<print_v->name;
    cout <<'\n' <<"Цена пути: " <<tgt->priority <<'\n' <<'\n';
}
 
void Graph::pred_search()
{
    vertex *cur_v = vert_list->next_vert;
    while (cur_v) {
        cur_v->pred_vert = nullptr;
        cur_v = cur_v->next_vert;
    }
}
 
 
void Graph::get_eccent(vertex *_vert)
{
    Queue Q(num_vert);
    Q.enqueue(_vert);
 
    int ecc = 0;
    _vert->dist = 0;
    vertex *deq_v;
    edge *cur_e;
    while (!Q.is_empty()) {
        deq_v = Q.dequeue();
        if (deq_v->dist > ecc) {
            ecc = deq_v->dist;
        }
        cur_e = deq_v->edge_list->next_edge;
        while (cur_e) {
            if (!cur_e->neighbour->was_in_queue) {
                cur_e->neighbour->dist = deq_v->dist+1;
                Q.enqueue(cur_e->neighbour);
            }
            cur_e = cur_e->next_edge;
        }
    }
    _vert->eccent = ecc;
 
    vertex *cur_v = vert_list->next_vert;
    while (cur_v) {
        cur_v->was_in_queue = false;
        cur_v = cur_v->next_vert;
    }
}
 
void Graph::prepare_draw() 
{
    vertex *cur_v = vert_list->next_vert;
    while (cur_v) {
        get_eccent(cur_v);
        cur_v = cur_v->next_vert;
    }
 
    SortByEccent();
}
Добавлено через 2 минуты
Ах да, еще нужна очередь с приоритетами.

хедр:
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
#ifndef PRIOR_QUEUE_H
#define PRIOR_QUEUE_H
 
#include "Graph.h"
 
using namespace std;
 
class vertex;
 
class Prior_Queue  //очередь - список.
{
private:
    vertex *q_vert;
    Prior_Queue *next_q;
 
public:
    Prior_Queue();
    Prior_Queue(vertex*, Prior_Queue*);
    ~Prior_Queue();
 
    bool is_empty();  //пуста ли очередь;
    void enqueue_vert(vertex*, vertex*);   //добавить вершину.
    vertex* dequeue_vert();   //извлечь вершину с наименьшим приоритетом.
    bool search_vert(vertex*); //поиск вершины в очереди (проверка наличия).
    void clear();  //очистить очередь.
};
 
#endif
cpp:
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
#include "Graph.h"
#include "Prior_Queue.h"
 
Prior_Queue::Prior_Queue() 
{
    q_vert = nullptr;
    next_q = nullptr;
}
 
Prior_Queue::Prior_Queue(vertex *Vert, Prior_Queue *Next)
{
    q_vert = Vert;
    next_q = Next;
}
 
Prior_Queue::~Prior_Queue()
{
}
 
bool Prior_Queue::is_empty()
{
    return (next_q == nullptr);
}
 
void Prior_Queue::enqueue_vert(vertex *enq_v, vertex *pr_vert)
{
    int prior = enq_v->get_prior(pr_vert);
    enq_v->priority = prior;
    next_q = new Prior_Queue(enq_v, next_q);
}
 
vertex* Prior_Queue::dequeue_vert()
{
    Prior_Queue *q_prev = this, *q_cur = next_q;
    int min_prior = q_cur->q_vert->priority;
    Prior_Queue *q_deq_prev = q_prev, *q_deq = q_cur;
    while (q_cur) {     //ищем элемент с наименьшим приоритетом.
        if (q_cur->q_vert->priority < min_prior) {
            min_prior = q_cur->q_vert->priority;
            q_deq_prev = q_prev;
            q_deq = q_cur;
        }
        q_prev = q_cur;
        q_cur = q_cur->next_q;
    }
 
    q_deq_prev->next_q = q_deq->next_q;
    vertex *ret_vert = q_deq->q_vert;
    delete q_deq;                               
 
    return ret_vert;
}
 
bool Prior_Queue::search_vert(vertex *search_v)
{
    Prior_Queue *q_cur = next_q;
    while (q_cur) {
        if (q_cur->q_vert = search_v) {
            return true;
        }
        q_cur = q_cur->next_q;
    }
    return false;
}
 
void Prior_Queue::clear()
{
    Prior_Queue *q_del = next_q;
    if (q_del) {  //если очередь не пуста.
        Prior_Queue *q_cur = next_q->next_q;
        while (q_cur) {  //очищаем очередь.
            delete q_del;
            q_del = q_cur;
            q_cur = q_cur->next_q;
        }
        delete q_del;
        next_q = nullptr;
    }
}
 
Текущее время: 22:39. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru