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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 35, средняя оценка - 4.97
kukhtikov
2 / 2 / 0
Регистрация: 16.12.2012
Сообщений: 97
04.05.2013, 08:26     Алгоритм Дейкстры #1
Как на С++ в консольном приложении описать алгоритм Дейкстры?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.05.2013, 08:26     Алгоритм Дейкстры
Посмотрите здесь:

Алгоритм Дейкстры C++
Алгоритм Дейкстры C++
C++ Алгоритм Дейкстры
Алгоритм Дейкстры С++ C++
C++ Алгоритм Дейкстры
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
BumerangSP
 Аватар для BumerangSP
4283 / 1405 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
04.05.2013, 13:18     Алгоритм Дейкстры #2
Может, что из этого подойдет.
Алгоритм Дейкстры
Алгоритм Дейкстры
Будет ли отличаться алгоритм Дейкстры от подсчета расстояний в ориентированной ненагруженном графе?
алгоритм дейкстры
kukhtikov
2 / 2 / 0
Регистрация: 16.12.2012
Сообщений: 97
05.05.2013, 02:47  [ТС]     Алгоритм Дейкстры #3
BumerangSP, во всех программах выдает ошибку доступа
BumerangSP
 Аватар для BumerangSP
4283 / 1405 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
05.05.2013, 11:29     Алгоритм Дейкстры #4
kukhtikov, потому что данные нужно из файла считывать.
eugrita
3 / 4 / 0
Регистрация: 18.11.2009
Сообщений: 405
05.05.2013, 12:05     Алгоритм Дейкстры #5
Мне известно несколько реализаций алг.Дейкстры, отличающиеся структурами используемых данных.
На входе у них как правило матрица смежности (весов) Отличаются использованием структур при реализации - списков, очередей, массивов. Все не сравнивал,но простейшая с массивами имеет некоторый недостаток -находит только одно минимальное дерево. Т.е возможны случаи когда в неориентированном графе на вход проге даешь
nach=i fin=j получаешь некий путь, затем меняешь местами nach=j fin=i и получаешь совсем другой путь
(правда их длины совпадают). Интересна модификация алгоритма выводящие все кратчайшие пути от i до j если их несколько)
kukhtikov
2 / 2 / 0
Регистрация: 16.12.2012
Сообщений: 97
05.05.2013, 19:10  [ТС]     Алгоритм Дейкстры #6
eugrita, мне бы самую простую реализацию
eugrita
3 / 4 / 0
Регистрация: 18.11.2009
Сообщений: 405
06.05.2013, 08:54     Алгоритм Дейкстры #7
вот простая под C++ практически годится под C если заменить операторы типа
for(int i=....). Пара фунций - печать массива и чтение исх данных из файла - для удобства работы
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
#include <math.h>
#include <stdio.h>
#include <conio.h>
const float INF = 30000;
float ** a;  int *pr;
 void readDan(int *n) {//чтение из файла матрицы
  int m; FILE * f=fopen("dan.txt","r");
if (f==NULL)
{ printf("Error!!! File not found! Press any key to exit");getch();return;}
  fscanf(f,"%i",&m);
  a=new float *[m];
  for (int i=0;i<m;i++)
    for (int j=0;j<m;j++)
       a[i]=new float[m];
  for (int i=0;i<m;i++)
       for (int j=0;j<m;j++)
       {
        fscanf(f,"%f",&a[i][j]);
        if (a[i][j]==-1) a[i][j]=INF;
       }
 fclose(f);  *n=m;
                     }
 void printA(int n) {
   for (int i = 0; i < n; i++) {
     for (int j = 0; j < n; j++)
      if (a[i][j]==INF) printf(" * ");
      else printf("%2.0f ",a[i][j]);
     printf("\n");
                               }
                    }
 
 void ShortPth(int n,int n1,int n2)   //n1-N нач верш. n2-конечная ,n-кол верш
 {//алг Дейкстры по маnh.Нах кратч расст по паре вершин графа до .
   float  *D; bool *flag;
     pr=new int[n]; D=new float[n];flag=new bool[n];
    for (int i = 0; i < n; i++)
       { pr[i] = n1; flag[i] = false; D[i] = a[n1][i]; }
    //Пока известно только одно расст:от верши nach  до нее же, равное 0.
    flag[n1] = true;    pr[n1] = 0;
    for (int i = 0; i < n - 1; i++) {//i
        int k = 0; float minras = 30000;
        // Находим минимальное расстояние до непомеченных вершин
        for (int j = 0; j < n; j++)       {//j
            if (!flag[j] && minras > D[j])
                  { minras = D[j]; k = j;}
                                          }//j
        flag[k] = true;  // Вершина k помечается просмотренной
        for (int j = 0; j < n; j++)      {//j
    //Если для верш j еще не найдено кратч расст от нач. и из вершины k по дуге A[k][j]
    //путь в j короче чем найденное ранее, то запоминаем его.
            if (!flag[j] && D[j] > D[k] + a[k][j])
                 { D[j] = D[k] + a[k][j];pr[j] = k;}
                                         }//j
                                     } //i
    printf("Rasstoyaniya ot %d do %d: %f\n", n1, n2, D[n2]);
 /*Выв путь задом наперед: в кажд эл масс pr хр N предыд яч-верш кратч пути.Напр,предыд верш для верш 5=pr[5]*/
        printf("\npath: from %d to %d: ", n2 , n1);
        int j=n2; printf("%d ", j);
        while (1==1) {
           j = pr[j];printf("%d ", j);
           if (j==n1) break;
                     }
 }
void main()
{  char c; int n,N1,N2;//n-кол верш
    readDan(&n);
    printf("load graph n=%i A=\n",n);printA(n);
    do {
    if(c=='0') return;
    printf("Nstart=? Nfin=? (ot 0 do %i)\n",n-1); scanf("%i %i",&N1,&N2);
    ShortPth(n,N1,N2);
    printf("\nEXIT-0\n");scanf("%c",&c);
       }  while(1==1);
}
kukhtikov
2 / 2 / 0
Регистрация: 16.12.2012
Сообщений: 97
06.05.2013, 12:55  [ТС]     Алгоритм Дейкстры #8
eugrita, спасибо!
Elizaveta19
0 / 0 / 0
Регистрация: 18.02.2014
Сообщений: 6
03.05.2014, 02:13     Алгоритм Дейкстры #9
пыталась переделать ваш код, чтобы он стал рабочим весь вечер, но так и не получилось. недостаток этого метода в том, что путь 2-1-4-5 (даже если это единственный путь из 2 в 5) он не найдет или найдет неправильно. то есть он ищет только "прямые" пути вроде 1-3-5
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.05.2014, 03:49     Алгоритм Дейкстры
Еще ссылки по теме:

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

Искать еще темы с ответами

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

хедр:
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;
    }
}
Yandex
Объявления
03.05.2014, 03:49     Алгоритм Дейкстры
Ответ Создать тему
Опции темы

Текущее время: 09:52. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru