teratail
回答率
85.47%
質問するログイン新規登録
トップに関する質問優先度付きキューを利用したダイクストラ法のアルゴリズムのプログラムを作成したいです。

編集履歴

質問編集履歴

4

ダイクストラ法のアルゴリズムにするためにプログラムを変えました。

2021/11/15 21:15

投稿

wagashi_157
wagashi_157

スコア51

test CHANGED
File without changes
test CHANGED
@@ -64,6 +64,8 @@
64
64
 
65
65
  #define N 30
66
66
 
67
+ #define DENSITY 9
68
+
67
69
  #define MAX_COST 100
68
70
 
69
71
 
@@ -76,6 +78,14 @@
76
78
 
77
79
  };
78
80
 
81
+ struct to_len {
82
+
83
+ int to, len;
84
+
85
+ };
86
+
87
+ list<to_len> vList[N];
88
+
79
89
 
80
90
 
81
91
  node node_data[N];
@@ -124,6 +134,64 @@
124
134
 
125
135
 
126
136
 
137
+ void down_heap(int parent)
138
+
139
+ {
140
+
141
+ if (left(parent)>heap_size-1) return;
142
+
143
+
144
+
145
+ if (left(parent)==heap_size-1) {
146
+
147
+ if (node_data[parent].cost>node_data[left(parent)].cost) {
148
+
149
+ node_idx[node_data[parent].id] = left(parent);
150
+
151
+ node_idx[node_data[left(parent)].id] = parent;
152
+
153
+ swap(node_data[parent],node_data[left(parent)]);
154
+
155
+ down_heap(left(parent));
156
+
157
+ }
158
+
159
+ } else {
160
+
161
+ if (node_data[left(parent)].cost<=node_data[right(parent)].cost) {
162
+
163
+ if (node_data[parent].cost>node_data[left(parent)].cost) {
164
+
165
+ node_idx[node_data[parent].id] = left(parent);
166
+
167
+ node_idx[node_data[left(parent)].id] = parent;
168
+
169
+ swap(node_data[parent],node_data[left(parent)]);
170
+
171
+ down_heap(left(parent));
172
+
173
+ }
174
+
175
+ } else {
176
+
177
+ if (node_data[parent].cost>node_data[right(parent)].cost) {
178
+
179
+ node_idx[node_data[parent].id] = right(parent);
180
+
181
+ node_idx[node_data[right(parent)].id] = parent;
182
+
183
+ swap(node_data[parent],node_data[right(parent)]);
184
+
185
+ down_heap(right(parent));
186
+
187
+ }
188
+
189
+ }
190
+
191
+ }
192
+
193
+ }
194
+
127
195
  void up_heap(int child)
128
196
 
129
197
  {
@@ -184,17 +252,17 @@
184
252
 
185
253
  }
186
254
 
187
-
188
-
189
255
  void make_heap()
190
256
 
191
257
  {
192
258
 
259
+ for (int i=(N-1)/2; i>=0; i--) {
260
+
193
- up_heap(N-1);
261
+ down_heap(i);
194
-
262
+
195
- }
263
+ }
264
+
196
-
265
+ }
197
-
198
266
 
199
267
  bool check_rightmost(int i)
200
268
 
@@ -214,36 +282,6 @@
214
282
 
215
283
  }
216
284
 
217
-
218
-
219
- void print_heap()
220
-
221
- {
222
-
223
- for (int i=0; i<heap_size; i++) {
224
-
225
- cout << "id: ";
226
-
227
- cout << node_data[i].id;
228
-
229
- cout << ", cost: ";
230
-
231
- cout << node_data[i].cost;
232
-
233
-
234
-
235
- if (check_rightmost(i)) cout << endl;
236
-
237
- else cout << " ";
238
-
239
- }
240
-
241
- cout << endl;
242
-
243
- }
244
-
245
-
246
-
247
285
  void push(int id, int cost)
248
286
 
249
287
  {
@@ -294,85 +332,77 @@
294
332
 
295
333
  }
296
334
 
297
-
298
-
299
335
  void change(int id, int cost)
300
336
 
301
337
  {
302
338
 
339
+ int old;
340
+
341
+ old=node_data[node_idx[id]].cost;
342
+
303
343
  node_data[node_idx[id]].cost=cost;
304
344
 
305
- node_idx[node_data[node_idx[id]].id]=id;
345
+ if (old>node_data[node_idx[id]].cost) down_heap(node_idx[id]);
346
+
306
-
347
+ else up_heap(node_idx[id]);
348
+
307
- }
349
+ }
350
+
308
-
351
+ void print_path()
352
+
309
-
353
+ {
354
+
355
+ if (path[N-1] == -1)
356
+
357
+ cout << "Unreachable!" << endl;
358
+
359
+ else {
360
+
361
+ rec_print_path(N-1);
362
+
363
+ cout << endl;
364
+
365
+ cout << "cost: " << node_data[0].cost << endl;
366
+
367
+ }
368
+
369
+ }
370
+
371
+
372
+
373
+ void rec_print_path(int vertex)
374
+
375
+ {
376
+
377
+ path[0]=1;
378
+
379
+ for (auto next:graph[vertex]) {
380
+
381
+ if (path[next]==1) continue;
382
+
383
+ rec_print_path(next);
384
+
385
+ }
386
+
387
+ }
310
388
 
311
389
  int main()
312
390
 
313
391
  {
314
392
 
315
- gen_node_data();
393
+ gen_graph();
316
-
394
+
317
- print_heap();
395
+ print_graph();
318
-
319
- make_heap();
396
+
320
-
397
+
398
+
321
- print_heap();
399
+ init_heap();
322
-
323
-
324
-
325
- int op, id, cost;
400
+
326
-
327
- while (cout << "Input an operation number: 1:push, 2:pop, 3:change -> "
328
-
329
- && cin >> op) {
330
-
331
- switch (op) {
401
+ dijkstra();
332
-
333
- case 1: // push
402
+
334
-
335
- cout << "Input an ID number -> ";
403
+
336
-
337
- cin >> id;
404
+
338
-
339
- cout << "Input its cost -> ";
340
-
341
- cin >> cost;
342
-
343
- push(id, cost);
344
-
345
- break;
346
-
347
- case 2: // pop
348
-
349
- pop();
350
-
351
- break;
352
-
353
- case 3: // change
354
-
355
- cout << "Input an ID number -> ";
356
-
357
- cin >> id;
358
-
359
- cout << "Input its cost -> ";
360
-
361
- cin >> cost;
362
-
363
- change(id, cost);
364
-
365
- break;
366
-
367
- default:
368
-
369
- cout << "Input 1, 2, or 3." << endl;
370
-
371
- }
372
-
373
- print_heap();
405
+ print_path();
374
-
375
- }
376
406
 
377
407
 
378
408
 

3

プログラムを修正しました。

2021/11/15 21:15

投稿

wagashi_157
wagashi_157

スコア51

test CHANGED
File without changes
test CHANGED
@@ -58,23 +58,13 @@
58
58
 
59
59
  #include<random>
60
60
 
61
- #include<list>
62
-
63
61
  using namespace std;
64
62
 
65
63
 
66
64
 
67
65
  #define N 30
68
66
 
69
- #define DENSITY 9
70
-
71
- #define MAX_COST 10
67
+ #define MAX_COST 100
72
-
73
-
74
-
75
- int graph[N][N]={0};
76
-
77
- int path[N]={0};
78
68
 
79
69
 
80
70
 
@@ -88,16 +78,6 @@
88
78
 
89
79
 
90
80
 
91
- struct to_len {
92
-
93
- int to, len;
94
-
95
- };
96
-
97
- list<to_len> vList[N];
98
-
99
-
100
-
101
81
  node node_data[N];
102
82
 
103
83
  int node_idx[N];
@@ -106,365 +86,293 @@
106
86
 
107
87
 
108
88
 
109
- void gen_graph()
89
+ void gen_node_data()
110
90
 
111
91
  {
112
92
 
113
93
  mt19937 mt{random_device{}()};
114
94
 
115
- uniform_int_distribution<int> dist(0,DENSITY);
116
-
117
- uniform_int_distribution<int> wdist(1,MAX_COST);
95
+ uniform_int_distribution<int> dist(0,MAX_COST);
118
-
96
+
119
- int len;
97
+ heap_size = 0;
120
-
121
-
122
-
98
+
99
+
100
+
123
- for (int i=0; i<N; i++)
101
+ for (int i=0; i<N; i++) {
124
-
102
+
125
- for (int j=i+1; j<N; j++)
103
+ node_data[i].id = i;
126
-
104
+
127
- graph[i][j] = dist(mt);
105
+ node_data[i].cost = dist(mt);
106
+
128
-
107
+ heap_size++;
108
+
109
+
110
+
129
-
111
+ node_idx[i] = i;
112
+
130
-
113
+ }
114
+
115
+ }
116
+
117
+
118
+
131
- for (int i=0; i<N; i++)
119
+ int left(int i) {return 2*i+1;}
132
-
120
+
133
- for (int j=i+1; j<N; j++)
121
+ int right(int i) {return 2*i+2;}
122
+
134
-
123
+ void swap(node &a, node &b) {node tmp=a; a=b; b=tmp;}
124
+
125
+
126
+
127
+ void up_heap(int child)
128
+
129
+ {
130
+
131
+ int parent=(child-1)/2;
132
+
133
+ if (child>heap_size-1) return;
134
+
135
+
136
+
135
- if (graph[i][j]==1) {
137
+ if (child==heap_size-1) {
138
+
136
-
139
+ if (node_data[parent].cost<node_data[child].cost) {
140
+
141
+ node_idx[node_data[parent].id] = child;
142
+
143
+ node_idx[node_data[child].id] = parent;
144
+
145
+ swap(node_data[parent],node_data[child]);
146
+
137
- len = wdist(mt);
147
+ up_heap(parent);
148
+
138
-
149
+ }
150
+
151
+ } else {
152
+
153
+ if (node_data[right(parent)].cost<=node_data[left(parent)].cost) {
154
+
155
+ if (node_data[left(parent)].cost>node_data[parent].cost) {
156
+
157
+ node_idx[node_data[parent].id] = left(parent);
158
+
159
+ node_idx[node_data[left(parent)].id] = parent;
160
+
161
+ swap(node_data[parent],node_data[left(parent)]);
162
+
139
- vList[i].push_back({j,len});
163
+ up_heap(parent);
140
-
141
- vList[j].push_back({i,len});
142
164
 
143
165
  }
144
166
 
145
-
167
+ } else {
168
+
146
-
169
+ if (node_data[right(parent)].cost>node_data[parent].cost) {
170
+
147
- for (int i=0; i<N; i++)
171
+ node_idx[node_data[parent].id] = right(parent);
172
+
148
-
173
+ node_idx[node_data[right(parent)].id] = parent;
174
+
175
+ swap(node_data[parent],node_data[right(parent)]);
176
+
149
- path[i] = -1;
177
+ up_heap(parent);
150
-
178
+
151
- }
179
+ }
152
-
153
- int left(int i) {return 2*i+1;}
154
-
155
- int right(int i) {return 2*i+2;}
156
-
157
- void swap(node &a, node &b) {node tmp=a; a=b; b=tmp;}
158
-
159
-
160
-
161
- void down_heap(int parent)
162
-
163
- {
164
-
165
- if (left(parent)>heap_size-1) return;
166
-
167
-
168
-
169
- if (left(parent)==heap_size-1) {
170
-
171
- if (node_data[parent].cost>node_data[left(parent)].cost) {
172
-
173
- node_idx[node_data[parent].id] = left(parent);
174
-
175
- node_idx[node_data[left(parent)].id] = parent;
176
-
177
- swap(node_data[parent],node_data[left(parent)]);
178
-
179
- down_heap(left(parent));
180
180
 
181
181
  }
182
182
 
183
- } else {
184
-
185
- if (node_data[left(parent)].cost<=node_data[right(parent)].cost) {
186
-
187
- if (node_data[parent].cost>node_data[left(parent)].cost) {
188
-
189
- node_idx[node_data[parent].id] = left(parent);
190
-
191
- node_idx[node_data[left(parent)].id] = parent;
192
-
193
- swap(node_data[parent],node_data[left(parent)]);
194
-
195
- down_heap(left(parent));
196
-
197
- }
198
-
199
- } else {
200
-
201
- if (node_data[parent].cost>node_data[right(parent)].cost) {
202
-
203
- node_idx[node_data[parent].id] = right(parent);
204
-
205
- node_idx[node_data[right(parent)].id] = parent;
206
-
207
- swap(node_data[parent],node_data[right(parent)]);
208
-
209
- down_heap(right(parent));
210
-
211
- }
183
+ }
184
+
185
+ }
186
+
187
+
188
+
189
+ void make_heap()
190
+
191
+ {
192
+
193
+ up_heap(N-1);
194
+
195
+ }
196
+
197
+
198
+
199
+ bool check_rightmost(int i)
200
+
201
+ {
202
+
203
+ int x = i+2;
204
+
205
+ while (x>1) {
206
+
207
+ if (x%2==1) return 0;
208
+
209
+ else x=x/2;
210
+
211
+ }
212
+
213
+ return 1;
214
+
215
+ }
216
+
217
+
218
+
219
+ void print_heap()
220
+
221
+ {
222
+
223
+ for (int i=0; i<heap_size; i++) {
224
+
225
+ cout << "id: ";
226
+
227
+ cout << node_data[i].id;
228
+
229
+ cout << ", cost: ";
230
+
231
+ cout << node_data[i].cost;
232
+
233
+
234
+
235
+ if (check_rightmost(i)) cout << endl;
236
+
237
+ else cout << " ";
238
+
239
+ }
240
+
241
+ cout << endl;
242
+
243
+ }
244
+
245
+
246
+
247
+ void push(int id, int cost)
248
+
249
+ {
250
+
251
+ for (int i=0; i<N-1; i++) {
252
+
253
+ node_data[i].id=node_data[i+1].id;
254
+
255
+ node_data[i].cost=node_data[i+1].cost;
256
+
257
+ }
258
+
259
+ for (int i=0; i<N-1; i++) {
260
+
261
+ node_idx[node_data[i].id]=node_data[i].id;
262
+
263
+ }
264
+
265
+ node_data[N-1].id=id;
266
+
267
+ node_data[N-1].cost=cost;
268
+
269
+ node_idx[node_data[N-1].id]=node_data[N-1].id;
270
+
271
+ }
272
+
273
+
274
+
275
+ void pop()
276
+
277
+ {
278
+
279
+ for (int i=0; i<N-1; i++) {
280
+
281
+ node_data[i].id=node_data[i+1].id;
282
+
283
+ node_data[i].cost=node_data[i+1].cost;
284
+
285
+ }
286
+
287
+ for (int i=0; i<N-1; i++) {
288
+
289
+ node_idx[node_data[i].id]=node_data[i].id;
290
+
291
+ }
292
+
293
+ node_idx[node_data[N-1].id]=node_data[N-1].id;
294
+
295
+ }
296
+
297
+
298
+
299
+ void change(int id, int cost)
300
+
301
+ {
302
+
303
+ node_data[node_idx[id]].cost=cost;
304
+
305
+ node_idx[node_data[node_idx[id]].id]=id;
306
+
307
+ }
308
+
309
+
310
+
311
+ int main()
312
+
313
+ {
314
+
315
+ gen_node_data();
316
+
317
+ print_heap();
318
+
319
+ make_heap();
320
+
321
+ print_heap();
322
+
323
+
324
+
325
+ int op, id, cost;
326
+
327
+ while (cout << "Input an operation number: 1:push, 2:pop, 3:change -> "
328
+
329
+ && cin >> op) {
330
+
331
+ switch (op) {
332
+
333
+ case 1: // push
334
+
335
+ cout << "Input an ID number -> ";
336
+
337
+ cin >> id;
338
+
339
+ cout << "Input its cost -> ";
340
+
341
+ cin >> cost;
342
+
343
+ push(id, cost);
344
+
345
+ break;
346
+
347
+ case 2: // pop
348
+
349
+ pop();
350
+
351
+ break;
352
+
353
+ case 3: // change
354
+
355
+ cout << "Input an ID number -> ";
356
+
357
+ cin >> id;
358
+
359
+ cout << "Input its cost -> ";
360
+
361
+ cin >> cost;
362
+
363
+ change(id, cost);
364
+
365
+ break;
366
+
367
+ default:
368
+
369
+ cout << "Input 1, 2, or 3." << endl;
212
370
 
213
371
  }
214
372
 
373
+ print_heap();
374
+
215
- }
375
+ }
216
-
217
- }
218
-
219
-
220
-
221
- void up_heap(int child)
222
-
223
- {
224
-
225
- int t;
226
-
227
- while (child>0) {
228
-
229
- if (node_idx[child/2]>node_idx[child]) {
230
-
231
- t=node_idx[child/2];
232
-
233
- node_idx[child/2]=node_idx[child];
234
-
235
- node_idx[child]=t;
236
-
237
- }
238
-
239
- child=child/2;
240
-
241
- }
242
-
243
- }
244
-
245
-
246
-
247
- void init_heap()
248
-
249
- {
250
-
251
- node_data[0].id = 0;
252
-
253
- node_data[0].cost = 0;
254
-
255
- heap_size = 1;
256
-
257
-
258
-
259
- for (int i=1; i<N; i++) {
260
-
261
- node_data[i].id = i;
262
-
263
- node_data[i].cost = MAX_COST*N;
264
-
265
- heap_size++;
266
-
267
-
268
-
269
- node_idx[i] = i;
270
-
271
- }
272
-
273
- }
274
-
275
-
276
-
277
- void push(int id, int cost)
278
-
279
- {
280
-
281
- for (int i=0; i<N-1; i++) {
282
-
283
- node_data[i].id=node_data[i+1].id;
284
-
285
- node_data[i].cost=node_data[i+1].cost;
286
-
287
- }
288
-
289
- node_data[N-1].id=id;
290
-
291
- node_data[N-1].cost=cost;
292
-
293
- }
294
-
295
-
296
-
297
- void pop()
298
-
299
- {
300
-
301
- for (int i=0; i<N-1; i++) {
302
-
303
- node_data[i].id=node_data[i+1].id;
304
-
305
- node_data[i].cost=node_data[i+1].cost;
306
-
307
- }
308
-
309
- node_data[N-1].id=0;
310
-
311
- node_data[N-1].cost=0;
312
-
313
- }
314
-
315
-
316
-
317
- void change(int id, int cost)
318
-
319
- {
320
-
321
- node_data[node_idx[id]].cost=cost;
322
-
323
- }
324
-
325
-
326
-
327
- void dijkstra()
328
-
329
- {
330
-
331
- int s,j,minlen,m;
332
-
333
- for (j=0; j<N; j++) {
334
-
335
- for (auto it{vList[m].begin()}; it!=vList[m].end(); ++it) {
336
-
337
- path[j]=9999;
338
-
339
- s=0;
340
-
341
- (*it).len=0;
342
-
343
- }
344
-
345
- }
346
-
347
- for (m=0; m<N; m++) {
348
-
349
- path[s]=1;
350
-
351
- for (auto it{vList[m].begin()}; it!=vList[m].end(); ++it) {
352
-
353
- if (graph[s][j]!=1) continue;
354
-
355
- if ((*it).len+graph[s][j]<(*it).len) (*it).len=(*it).len+graph[it][j];
356
-
357
- }
358
-
359
- minlen=9999;
360
-
361
- for (auto it{vList[m].begin()}; it!=vList[m].end(); ++it) {
362
-
363
- if (path[j]==1) continue;
364
-
365
- if ((*it).len<minlen) {minlen=j; it=j;}
366
-
367
- }
368
-
369
- }
370
-
371
- }
372
-
373
-
374
-
375
- void print_graph()
376
-
377
- {
378
-
379
- for (int i=0; i<N; i++) {
380
-
381
- for (int j=0; j<N; j++)
382
-
383
- cout << (graph[i][j]!=0) << " ";
384
-
385
- cout << endl;
386
-
387
- }
388
-
389
- cout << endl;
390
-
391
-
392
-
393
- for (int i=0; i<N; i++) {
394
-
395
- cout << i << ": ";
396
-
397
- for (auto itr=vList[i].begin(); itr!=vList[i].end(); ++itr)
398
-
399
- cout << (*itr).to << " ";
400
-
401
- cout << endl;
402
-
403
- }
404
-
405
- cout << endl;
406
-
407
- }
408
-
409
-
410
-
411
- void rec_print_path(int vertex)
412
-
413
- {
414
-
415
- path[0]=1;
416
-
417
- for (auto next:graph[vertex]) {
418
-
419
- if (path[next]==1) continue;
420
-
421
- rec_print_path(next);
422
-
423
- }
424
-
425
- }
426
-
427
-
428
-
429
- void print_path()
430
-
431
- {
432
-
433
- if (path[N-1] == -1)
434
-
435
- cout << "Unreachable!" << endl;
436
-
437
- else {
438
-
439
- rec_print_path(N-1);
440
-
441
- cout << endl;
442
-
443
- cout << "cost: " << node_data[0].cost << endl;
444
-
445
- }
446
-
447
- }
448
-
449
-
450
-
451
- int main()
452
-
453
- {
454
-
455
- gen_graph();
456
-
457
- print_graph();
458
-
459
-
460
-
461
- init_heap();
462
-
463
- dijkstra();
464
-
465
-
466
-
467
- print_path();
468
376
 
469
377
 
470
378
 
@@ -472,6 +380,8 @@
472
380
 
473
381
  }
474
382
 
383
+
384
+
475
385
  ```
476
386
 
477
387
  ### 試したこと

2

pop,push,changeは解決できたのでdijkstra関数や到達可能を判定するためのプログラムを解決したいということを追記しました。

2021/11/15 10:06

投稿

wagashi_157
wagashi_157

スコア51

test CHANGED
File without changes
test CHANGED
@@ -1,6 +1,6 @@
1
1
  ### 前提・実現したいこと
2
2
 
3
- 以下の要領にしたがって優先度付きキューを適切に利用したダイクストラ法のアルゴリズムを実装したいです。
3
+ 以下の要領を基に優先度付きキューを適切に利用したダイクストラ法のアルゴリズムを実装しようと思っています。
4
4
 
5
5
  1. まず，３０個の頂点上のグラフを保持する二次元配列graph[N][N]，及び，その隣接リストvList[N]，更に，最短経路木を保持する一次元配列path[N] を（大域変数として）用意する．
6
6
 
@@ -14,196 +14,42 @@
14
14
 
15
15
  ### 発生している問題・エラーメッセージ
16
16
 
17
- popやpushのうち構造体の扱い方でエラーが出ており, 到達可能を始めから順に出力するためのrec_print_pathの表現の仕方が分からず困っています。
17
+ push,pop,changeのプログラムは解決できましたが, 到達可能を判定するためのrec_print_pathの表現の仕方が分からず困っています(print_pathにもあるようにvoid関数で実装したいです)。それとlist関数を使ってdijkstra()を実装したいのですが, イテレータで表現してもエラーが出てしまい, 原因が分かりません。イテレーターに慣れていないのとダイクストラ法で図は描けるもののプログラムとなると中々上手くいかないので教えてほしいです。
18
18
 
19
19
  ```
20
20
 
21
- dijkstra.cpp: 関数 ‘void down_heap(int)’ 内:
22
-
23
- dijkstra.cpp:52:17: エラー: invalid initialization of reference of type ‘std::ios_base&’ from expression of type ‘int’
24
-
25
- if (left(parent)>heap_size-1) return;
26
-
27
- ^
28
-
29
- 備考: in passing argument 1 of ‘std::ios_base& std::left(std::ios_base&)’
30
-
31
- left(ios_base& __base)
32
-
33
- ^~~~
34
-
35
- dijkstra.cpp:54:17: エラー: invalid initialization of reference of type ‘std::ios_base&’ from expression of type ‘int’
36
-
37
- if (left(parent)==heap_size-1) {
38
-
39
- ^
40
-
41
- dijkstra.cpp:56:48: エラー: invalid initialization of reference of type ‘std::ios_base&’ from expression of type ‘int’
42
-
43
- node_idx[node_data[parent].id] = left(parent);
44
-
45
- ^
46
-
47
-
48
-
49
- dijkstra.cpp:59:25: エラー: invalid initialization of reference of type ‘std::ios_base&’ from expression of type ‘int’
50
-
51
- down_heap(left(parent));
52
-
53
- ^
54
-
55
- In file included ･･････
56
-
57
- /usr/lib/gcc/i686-pc-cygwin/7.4.0/include/c++/bits/ios_base.h:999:3: 備考: in passing argument 1 of ‘std::ios_base& std::left(std::ios_base&)’
58
-
59
- left(ios_base& __base)
60
-
61
- ^~~~
62
-
63
- dijkstra.cpp:62:28: エラー: invalid initialization of reference of type ‘std::ios_base&’ from expression of type ‘int’
64
-
65
- if (node_data[left(parent)].cost<=node_data[right(parent)].cost) {
66
-
67
- ^
68
-
69
- In file included ･･････
70
-
71
- /usr/lib/gcc/i686-pc-cygwin/7.4.0/include/c++/bits/ios_base.h:1007:3: 備考: in passing argument 1 of ‘std::ios_base& std::right(std::ios_base&)’
72
-
73
- right(ios_base& __base)
74
-
75
- ^~~~~
76
-
77
- dijkstra.cpp:63:52: エラー: invalid initialization of reference of type ‘std::ios_base&’ from expression of type ‘int’
78
-
79
- if (node_data[parent].cost>node_data[left(parent)].cost) {
80
-
81
- ^
82
-
83
-
84
-
85
- dijkstra.cpp:65:35: エラー: invalid initialization of reference of type ‘std::ios_base&’ from expression of type ‘int’
86
-
87
- node_idx[node_data[left(parent)].id] = parent;
88
-
89
- ^
90
-
91
- In file included from /usr/lib/gcc/i686-pc-cygwin/7.4.0/include/c++/ios:42:0,
92
-
93
- from /usr/lib/gcc/i686-pc-cygwin/7.4.0/include/c++/ostream:38,
94
-
95
- from /usr/lib/gcc/i686-pc-cygwin/7.4.0/include/c++/iostream:39,
96
-
97
- from dijkstra.cpp:1:
98
-
99
- /usr/lib/gcc/i686-pc-cygwin/7.4.0/include/c++/bits/ios_base.h:999:3: 備考: in passing argument 1 of ‘std::ios_base& std::left(std::ios_base&)’
100
-
101
- left(ios_base& __base)
102
-
103
- ^~~~
104
-
105
- dijkstra.cpp:66:49: エラー: invalid initialization of reference of type ‘std::ios_base&’ from expression of type ‘int’
106
-
107
- swap(node_data[parent],node_data[left(parent)]);
108
-
109
- ^
110
-
111
-
112
-
113
- dijkstra.cpp:74:27: エラー: invalid initialization of reference of type ‘std::ios_base&’ from expression of type ‘int’
114
-
115
- down_heap(right(parent));
116
-
117
- ^
118
-
119
- In file included ･･････
120
-
121
- /usr/lib/gcc/i686-pc-cygwin/7.4.0/include/c++/bits/ios_base.h:1007:3: 備考: in passing argument 1 of ‘std::ios_base& std::right(std::ios_base&)’
122
-
123
- right(ios_base& __base)
124
-
125
- ^~~~~
126
-
127
- dijkstra.cpp: 関数 ‘void push(int, int)’ 内:
128
-
129
- dijkstra.cpp:110:6: エラー: expected unqualified-id before ‘.’ token
130
-
131
- node.push_back({id,cost});
132
-
133
- ^
134
-
135
- dijkstra.cpp:110:26: エラー: expected primary-expression before ‘)’ token
136
-
137
- node.push_back({id,cost});
138
-
139
- ^
140
-
141
- dijkstra.cpp: 関数 ‘void pop()’ 内:
142
-
143
- dijkstra.cpp:115:6: エラー: expected unqualified-id before ‘.’ token
144
-
145
- node.pop_front();
146
-
147
- ^
148
-
149
- dijkstra.cpp: 関数 ‘void change(int, int)’ 内:
150
-
151
- dijkstra.cpp:120:22: エラー: expected primary-expression before ‘.’ token
152
-
153
- for (int i=0; i<node.size(); i++) {
154
-
155
- ^
156
-
157
- dijkstra.cpp:121:28: エラー: request for member ‘cost’ in ‘node_idx[i]’, which is of non-class type ‘int’
158
-
159
- node_data[i]=node_idx[i].cost;
160
-
161
- ^~~~
162
-
163
21
  dijkstra.cpp: 関数 ‘void dijkstra()’ 内:
164
22
 
165
- dijkstra.cpp:129:3: エラー: ‘u’ was not declared in this scope
166
-
167
- u[j]=9999;
168
-
169
- dijkstra.cpp:136:56: エラー: ‘class std::list<to_len>’ has no member named ‘len’; did you mean ‘cend’?
23
+ dijkstra.cpp:151:66: エラー: no match for ‘operator[]’ (operand types are ‘int [30][30]’ and ‘std::_List_iterator<to_len>’)
170
-
24
+
171
- if (vList[s].len+graph[s][j]<vList[j].len) vList[j].len=vList[s].len+graph[s][j];
25
+ if ((*it).len+graph[s][j]<(*it).len) (*it).len=(*it).len+graph[it][j];
172
-
173
- dijkstra.cpp:141:17: エラー: ‘class std::list<to_len>’ has no member named ‘len’; did you mean ‘cend’?
26
+
174
-
175
- if (vList[j].len<minlen) {minlen=j; s=j;}
176
-
177
- ^~~
178
-
179
- cend
180
-
181
- dijkstra.cpp:147:1: エラー: a function-definition is not allowed here before ‘{’ token
182
-
183
- {
184
-
185
- ^
27
+ ^
186
-
28
+
187
- dijkstra.cpp:165:1: エラー: a function-definition is not allowed here before ‘{’ token
29
+ dijkstra.cpp:156:40: エラー: no match for ‘operator=’ (operand types are ‘std::_List_iterator<to_len>’ and ‘int’)
188
-
30
+
189
- {
31
+ if ((*it).len<minlen) {minlen=j; it=j;}
190
-
32
+
191
- ^
33
+ ^
34
+
192
-
35
+ In file included from /usr/lib/gcc/i686-pc-cygwin/7.4.0/include/c++/list:63:0,
36
+
193
- dijkstra.cpp:170:1: エラー: 同上
37
+ from dijkstra.cpp:3:
38
+
194
-
39
+ /usr/lib/gcc/i686-pc-cygwin/7.4.0/include/c++/bits/stl_list.h:128:12: 備考: candidate: constexpr std::_List_iterator<to_len>& std::_List_iterator<to_len>::operator=(const std::_List_iterator<to_len>&)
195
-
196
-
40
+
197
- dijkstra.cpp:181:1: エラー: 同上
41
+ struct _List_iterator
198
-
42
+
199
- dijkstra.cpp:191:1: エラー: 同上
43
+ ^~~~~~~~~~~~~~
44
+
200
-
45
+ /usr/lib/gcc/i686-pc-cygwin/7.4.0/include/c++/bits/stl_list.h:128:12: 備考: 第 1 引数を ‘int’ から ‘const std::_List_iterator<to_len>&’ へ変換する方法が不明です
46
+
47
+ /usr/lib/gcc/i686-pc-cygwin/7.4.0/include/c++/bits/stl_list.h:128:12: 備考: candidate: constexpr std::_List_iterator<to_len>& std::_List_iterator<to_len>::operator=(std::_List_iterator<to_len>&&)
48
+
201
- ^
49
+ /usr/lib/gcc/i686-pc-cygwin/7.4.0/include/c++/bits/stl_list.h:128:12: 備考: 第 1 引数を ‘int’ から ‘std::_List_iterator<to_len>&&’ へ変換する方法が不明です
202
50
 
203
51
  ```
204
52
 
205
- ※字数の関係上省略したところがあります。
206
-
207
53
  ### 該当のソースコード
208
54
 
209
55
  ```C++
@@ -304,6 +150,12 @@
304
150
 
305
151
  }
306
152
 
153
+ int left(int i) {return 2*i+1;}
154
+
155
+ int right(int i) {return 2*i+2;}
156
+
157
+ void swap(node &a, node &b) {node tmp=a; a=b; b=tmp;}
158
+
307
159
 
308
160
 
309
161
  void down_heap(int parent)
@@ -426,7 +278,17 @@
426
278
 
427
279
  {
428
280
 
281
+ for (int i=0; i<N-1; i++) {
282
+
283
+ node_data[i].id=node_data[i+1].id;
284
+
285
+ node_data[i].cost=node_data[i+1].cost;
286
+
287
+ }
288
+
289
+ node_data[N-1].id=id;
290
+
429
- node.push_back({id,cost});
291
+ node_data[N-1].cost=cost;
430
292
 
431
293
  }
432
294
 
@@ -436,7 +298,17 @@
436
298
 
437
299
  {
438
300
 
301
+ for (int i=0; i<N-1; i++) {
302
+
303
+ node_data[i].id=node_data[i+1].id;
304
+
305
+ node_data[i].cost=node_data[i+1].cost;
306
+
307
+ }
308
+
309
+ node_data[N-1].id=0;
310
+
439
- node.pop_front();
311
+ node_data[N-1].cost=0;
440
312
 
441
313
  }
442
314
 
@@ -446,11 +318,7 @@
446
318
 
447
319
  {
448
320
 
449
- for (int i=0; i<node.size(); i++) {
450
-
451
- node_data[i]=node_idx[i].cost;
321
+ node_data[node_idx[id]].cost=cost;
452
-
453
- }
454
322
 
455
323
  }
456
324
 
@@ -464,31 +332,37 @@
464
332
 
465
333
  for (j=0; j<N; j++) {
466
334
 
335
+ for (auto it{vList[m].begin()}; it!=vList[m].end(); ++it) {
336
+
467
- u[j]=9999;
337
+ path[j]=9999;
468
-
338
+
469
- s=0;
339
+ s=0;
470
-
340
+
471
- vList[s].len=0;
341
+ (*it).len=0;
342
+
472
-
343
+ }
344
+
345
+ }
346
+
473
- for (m=1; m<N; m++) {
347
+ for (m=0; m<N; m++) {
474
348
 
475
349
  path[s]=1;
476
350
 
477
- for (j=0; j<N; j++) {
351
+ for (auto it{vList[m].begin()}; it!=vList[m].end(); ++it) {
478
352
 
479
353
  if (graph[s][j]!=1) continue;
480
354
 
481
- if (vList[s].len+graph[s][j]<vList[j].len) vList[j].len=vList[s].len+graph[s][j];
355
+ if ((*it).len+graph[s][j]<(*it).len) (*it).len=(*it).len+graph[it][j];
482
356
 
483
357
  }
484
358
 
485
359
  minlen=9999;
486
360
 
487
- for (j=0; j<N; j++) {
361
+ for (auto it{vList[m].begin()}; it!=vList[m].end(); ++it) {
488
362
 
489
363
  if (path[j]==1) continue;
490
364
 
491
- if (vList[j].len<minlen) {minlen=j; s=j;}
365
+ if ((*it).len<minlen) {minlen=j; it=j;}
492
366
 
493
367
  }
494
368
 
@@ -538,7 +412,15 @@
538
412
 
539
413
  {
540
414
 
415
+ path[0]=1;
416
+
417
+ for (auto next:graph[vertex]) {
418
+
419
+ if (path[next]==1) continue;
420
+
541
- node.push(vertex);
421
+ rec_print_path(next);
422
+
423
+ }
542
424
 
543
425
  }
544
426
 
@@ -594,7 +476,7 @@
594
476
 
595
477
  ### 試したこと
596
478
 
597
- nodeの構造体があることに留意しidとcostに分けて考えるほか, ダイクストラ法はvListとnode_dataとの関係に留意ながら値を設定しました(主にC言語のダイクストラ法を参考にしました。)。
479
+ イテレーターであるため, print_graph()を参考にdijkstra()を作成しました。rec_print_pathではfor(auto ...)を使って順に判定してみました。
598
480
 
599
481
  ### 補足情報（FW/ツールのバージョンなど）
600
482
 

1

字数の関係上エラーの文を省略したところがあるということを注釈で入れました。関数に_をつけました。

2021/11/14 16:21

投稿

wagashi_157
wagashi_157

スコア51

test CHANGED
File without changes
test CHANGED
@@ -4,9 +4,9 @@
4
4
 
5
5
  1. まず，３０個の頂点上のグラフを保持する二次元配列graph[N][N]，及び，その隣接リストvList[N]，更に，最短経路木を保持する一次元配列path[N] を（大域変数として）用意する．
6
6
 
7
- 2. グラフG = (V,E) をランダムに生成する．（巻末の付録を参照．）そのグラフを出力する．（これらを関数gen graph(), print graph() で行う．）
7
+ 2. グラフG = (V,E) をランダムに生成する．（巻末の付録を参照．）そのグラフを出力する．（これらを関数gen_graph(), print_graph() で行う．）
8
-
8
+
9
- 3. 優先度付きキューを初期化する．（これを関数init heap() で行う．）
9
+ 3. 優先度付きキューを初期化する．（これを関数init_heap() で行う．）
10
10
 
11
11
  4. 始点をs = 0，終点をt = 29 として，s からt への（G 上の）最短経路をダイクストラのアルゴリズムで探索する．（これを関数dijkstra() で行う．）
12
12
 
@@ -200,10 +200,10 @@
200
200
 
201
201
  ^
202
202
 
203
-
204
-
205
203
  ```
206
204
 
205
+ ※字数の関係上省略したところがあります。
206
+
207
207
  ### 該当のソースコード
208
208
 
209
209
  ```C++