1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file dijkstra.c
17 * @ingroup OTHER_CFILES
18 * @brief C implementation of Dijkstra's algorithm
19 * @author Thorsten Koch
20 * @author Marc Pfetsch
21 */
22
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24
25 #include <stdio.h>
26 #include <stdlib.h>
27 #include <assert.h>
28
29 #include "dijkstra.h"
30
31
32 /** Check whether the data structures of the graph are valid. */
dijkstraGraphIsValid(const DIJKSTRA_GRAPH * G)33 DIJKSTRA_Bool dijkstraGraphIsValid(
34 const DIJKSTRA_GRAPH* G /**< directed graph to be checked */
35 )
36 {
37 unsigned int count = 0;
38 unsigned int i;
39 unsigned int k;
40
41 if ( G == NULL || G->outbeg == NULL || G->outcnt == NULL || G->weight == NULL || G->head == NULL )
42 abort();
43
44 for (i = 0; i < G->nodes; ++i)
45 {
46 for (k = G->outbeg[i]; k < G->outbeg[i] + G->outcnt[i]; ++k)
47 {
48 if ( G->head[k] >= G->nodes )
49 abort();
50
51 if ( G->weight[k] > G->maxweight || G->weight[k] < G->minweight )
52 abort();
53
54 ++count;
55 }
56 if ( G->head[k] != DIJKSTRA_UNUSED )
57 abort();
58
59 ++count;
60 }
61 if ( count > G->arcs )
62 abort();
63
64 return TRUE;
65 }
66
67
68 #ifndef NDEBUG
69 /** Check whether heap is valid.
70 *
71 * @note Sift up/down do not use order, only for the last the changed one is entered.
72 */
73 static
dijkstraHeapIsValid(const unsigned int * entry,const unsigned long long * value,const unsigned int * order,const unsigned int used,const unsigned int size)74 DIJKSTRA_Bool dijkstraHeapIsValid(
75 const unsigned int* entry, /**< entries of heap */
76 const unsigned long long* value, /**< values in heap */
77 const unsigned int* order, /**< order of entries */
78 const unsigned int used, /**< number of used entries */
79 const unsigned int size /**< size of entry array */
80 )
81 {
82 unsigned int i;
83
84 if ( entry == NULL || value == NULL || order == NULL || used > size )
85 return FALSE;
86
87 /* check heap property */
88 for (i = 0; i < used / 2; ++i)
89 {
90 if ( value[entry[i]] > value[entry[i + i]] )
91 return FALSE;
92 if ( i + i + 1 < used && value[entry[i]] > value[entry[i + i + 1]] )
93 return FALSE;
94 }
95
96 return TRUE;
97 }
98 #endif
99
100
101 /** Moves an entry down in the vector until the sorting is valid again. */
102 static
dijkstraSiftDown(unsigned int * entry,const unsigned long long * value,unsigned int * order,unsigned int used,unsigned int current)103 void dijkstraSiftDown(
104 unsigned int* entry, /**< entries of heap */
105 const unsigned long long* value, /**< values in heap */
106 unsigned int* order, /**< order of entries */
107 unsigned int used, /**< number of used entries */
108 unsigned int current /**< current entry to be sifted */
109 )
110 {
111 unsigned long long val;
112 unsigned int child;
113 unsigned int ent;
114 unsigned int e;
115
116 child = current + current;
117 ent = entry[current];
118 val = value[ent];
119
120 while ( child < used )
121 {
122 e = entry[child];
123
124 if ( child + 1 < used )
125 {
126 if ( value[entry[child + 1]] < value[e] )
127 {
128 ++child;
129 e = entry[child];
130 }
131 }
132 if ( value[e] >= val )
133 break;
134
135 entry[current] = e;
136 order[e] = current;
137
138 current = child;
139 child += child;
140 }
141 entry[current] = ent;
142 order[ent] = current;
143 }
144
145
146 /** Moves an entry up in the vector until the sorting is valid again. */
147 static
dijkstraSiftUp(unsigned int * entry,const unsigned long long * value,unsigned int * order,unsigned int current)148 void dijkstraSiftUp(
149 unsigned int* entry, /**< entries of heap */
150 const unsigned long long* value, /**< values in heap */
151 unsigned int* order, /**< order of entries */
152 unsigned int current /**< current entry to be sifted */
153 )
154 {
155 unsigned long long val;
156 unsigned int parent;
157 unsigned int ent;
158 unsigned int e;
159
160 ent = entry[current];
161 val = value[ent];
162
163 while ( current > 0 )
164 {
165 parent = current / 2;
166 e = entry[parent];
167
168 if ( value[e] <= val )
169 break;
170
171 entry[current] = e;
172 order[e] = current;
173 current = parent;
174 }
175 entry[current] = ent;
176 order[ent] = current;
177 }
178
179
180 /** Dijkstra's algorithm for shortest paths from a single source using binary heaps */
dijkstra(const DIJKSTRA_GRAPH * G,unsigned int source,unsigned long long * dist,unsigned int * pred,unsigned int * entry,unsigned int * order)181 unsigned int dijkstra(
182 const DIJKSTRA_GRAPH* G, /**< directed graph */
183 unsigned int source, /**< source node */
184 unsigned long long* dist, /**< node distances (allocated by user) */
185 unsigned int* pred, /**< node predecessors in final shortest path tree (allocated by user) */
186 unsigned int* entry, /**< temporary storage (for each node - must be allocated by user) */
187 unsigned int* order /**< temporary storage (for each node - must be allocated by user) */
188 )
189 {
190 unsigned long long weight;
191 unsigned int iters = 0;
192 unsigned int used = 0;
193 unsigned int head;
194 unsigned int tail;
195 unsigned int i;
196 unsigned int e;
197
198 assert( dijkstraGraphIsValid(G) );
199 assert( source < G->nodes );
200 assert( dist != NULL );
201 assert( pred != NULL );
202
203 assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
204
205 /* initialize nodes */
206 for (i = 0; i < G->nodes; ++i)
207 {
208 dist[i] = DIJKSTRA_FARAWAY;
209 order[i] = DIJKSTRA_UNUSED;
210 pred[i] = DIJKSTRA_UNUSED;
211 }
212
213 /* enter source node into heap */
214 entry[0] = source;
215 order[source] = 0;
216 pred[source] = DIJKSTRA_UNUSED;
217 dist[source] = 0;
218
219 ++used;
220
221 /* loop while heap is not empty */
222 while ( used > 0 )
223 {
224 /* get next node */
225 tail = entry[0];
226
227 /* remove node from heap */
228 --used;
229 entry[0] = entry[used];
230 order[entry[0]] = 0;
231 order[tail] = DIJKSTRA_UNUSED;
232
233 dijkstraSiftDown(entry, dist, order, used, 0);
234
235 assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
236 assert( entry[used] < G->nodes );
237
238 /* check adjacent nodes */
239 for (e = G->outbeg[tail]; G->head[e] != DIJKSTRA_UNUSED; ++e)
240 {
241 head = G->head[e];
242 weight = G->weight[e] + dist[tail];
243
244 /* Can we improve the current shortest path? */
245 if ( dist[head] > weight )
246 {
247 assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
248 assert( used < G->nodes );
249 assert( head <= G->nodes );
250
251 pred[head] = tail;
252 dist[head] = weight;
253
254 if ( order[head] == DIJKSTRA_UNUSED )
255 {
256 assert( head < G->nodes );
257
258 entry[used] = head;
259 order[head] = used;
260
261 dijkstraSiftUp(entry, dist, order, used);
262 ++used;
263 }
264 else
265 {
266 dijkstraSiftUp(entry, dist, order, order[head]);
267 }
268 assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
269
270 ++iters;
271 }
272 }
273 }
274 assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
275
276 return iters;
277 }
278
279
280 /** Dijkstra's algorithm for shortest paths between a pair of nodes using binary heaps */
dijkstraPair(const DIJKSTRA_GRAPH * G,unsigned int source,unsigned int target,unsigned long long * dist,unsigned int * pred,unsigned int * entry,unsigned int * order)281 unsigned int dijkstraPair(
282 const DIJKSTRA_GRAPH* G, /**< directed graph */
283 unsigned int source, /**< source node */
284 unsigned int target, /**< target node */
285 unsigned long long* dist, /**< node distances (allocated by user) */
286 unsigned int* pred, /**< node predecessors in final shortest path tree (allocated by user) */
287 unsigned int* entry, /**< temporary storage (for each node - must be allocated by user) */
288 unsigned int* order /**< temporary storage (for each node - must be allocated by user) */
289 )
290 {
291 unsigned long long weight;
292 unsigned int iters = 0;
293 unsigned int used = 0;
294 unsigned int head;
295 unsigned int tail;
296 unsigned int i;
297 unsigned int e;
298
299 assert( dijkstraGraphIsValid(G) );
300 assert( source < G->nodes );
301 assert( target < G->nodes );
302 assert( dist != NULL );
303 assert( pred != NULL );
304
305 assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
306
307 /* initialize nodes */
308 for (i = 0; i < G->nodes; ++i)
309 {
310 dist[i] = DIJKSTRA_FARAWAY;
311 order[i] = DIJKSTRA_UNUSED;
312 pred[i] = DIJKSTRA_UNUSED;
313 }
314
315 /* enter source node into heap */
316 entry[0] = source;
317 order[source] = 0;
318 pred[source] = DIJKSTRA_UNUSED;
319 dist[source] = 0;
320
321 ++used;
322
323 /* loop while heap is not empty */
324 while ( used > 0 )
325 {
326 /* get next node */
327 tail = entry[0];
328
329 /* stop if we have found the target node */
330 if ( tail == target )
331 break;
332
333 /* remove node from heap */
334 --used;
335 entry[0] = entry[used];
336 order[entry[0]] = 0;
337 order[tail] = DIJKSTRA_UNUSED;
338
339 dijkstraSiftDown(entry, dist, order, used, 0);
340
341 assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
342 assert( entry[used] < G->nodes );
343
344 /* check adjacent nodes */
345 for (e = G->outbeg[tail]; G->head[e] != DIJKSTRA_UNUSED; ++e)
346 {
347 head = G->head[e];
348 weight = G->weight[e] + dist[tail];
349
350 /* Can we improve the current shortest path? */
351 if ( dist[head] > weight )
352 {
353 assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
354 assert( used < G->nodes );
355 assert( head <= G->nodes );
356
357 pred[head] = tail;
358 dist[head] = weight;
359
360 if ( order[head] == DIJKSTRA_UNUSED )
361 {
362 assert( head < G->nodes );
363
364 entry[used] = head;
365 order[head] = used;
366
367 dijkstraSiftUp(entry, dist, order, used);
368 ++used;
369 }
370 else
371 {
372 dijkstraSiftUp(entry, dist, order, order[head]);
373 }
374 assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
375
376 ++iters;
377 }
378 }
379 }
380 assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
381
382 return iters;
383 }
384
385
386 /** Dijkstra's algorithm for shortest paths between a pair of nodes using binary heaps and truncated at cutoff */
dijkstraPairCutoff(const DIJKSTRA_GRAPH * G,unsigned int source,unsigned int target,unsigned long long cutoff,unsigned long long * dist,unsigned int * pred,unsigned int * entry,unsigned int * order)387 unsigned int dijkstraPairCutoff(
388 const DIJKSTRA_GRAPH* G, /**< directed graph */
389 unsigned int source, /**< source node */
390 unsigned int target, /**< target node */
391 unsigned long long cutoff, /**< if the distance of a node reached this value, we truncate the search */
392 unsigned long long* dist, /**< node distances (allocated by user) */
393 unsigned int* pred, /**< node predecessors in final shortest path tree (allocated by user) */
394 unsigned int* entry, /**< temporary storage (for each node - must be allocated by user) */
395 unsigned int* order /**< temporary storage (for each node - must be allocated by user) */
396 )
397 {
398 unsigned long long weight;
399 unsigned int iters = 0;
400 unsigned int used = 0;
401 unsigned int head;
402 unsigned int tail;
403 unsigned int i;
404 unsigned int e;
405
406 assert( dijkstraGraphIsValid(G) );
407 assert( source < G->nodes );
408 assert( target < G->nodes );
409 assert( dist != NULL );
410 assert( pred != NULL );
411
412 assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
413
414 /* initialize nodes */
415 for (i = 0; i < G->nodes; ++i)
416 {
417 dist[i] = DIJKSTRA_FARAWAY;
418 order[i] = DIJKSTRA_UNUSED;
419 pred[i] = DIJKSTRA_UNUSED;
420 }
421
422 /* enter source node into heap */
423 entry[0] = source;
424 order[source] = 0;
425 pred[source] = DIJKSTRA_UNUSED;
426 dist[source] = 0;
427
428 ++used;
429
430 /* loop while heap is not empty */
431 while ( used > 0 )
432 {
433 /* get next node */
434 tail = entry[0];
435
436 /* stop if we have found the target node */
437 if ( tail == target )
438 break;
439
440 /* remove node from heap */
441 --used;
442 entry[0] = entry[used];
443 order[entry[0]] = 0;
444 order[tail] = DIJKSTRA_UNUSED;
445
446 dijkstraSiftDown(entry, dist, order, used, 0);
447
448 assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
449 assert( entry[used] < G->nodes );
450
451 /* only work on nodes if their distance is less than the cutoff */
452 if ( dist[tail] >= cutoff )
453 continue;
454
455 /* check adjacent nodes */
456 for (e = G->outbeg[tail]; G->head[e] != DIJKSTRA_UNUSED; ++e)
457 {
458 head = G->head[e];
459 weight = G->weight[e] + dist[tail];
460
461 /* Can we improve the current shortest path? */
462 if ( dist[head] > weight )
463 {
464 assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
465 assert( used < G->nodes );
466 assert( head <= G->nodes );
467
468 pred[head] = tail;
469 dist[head] = weight;
470
471 if ( order[head] == DIJKSTRA_UNUSED )
472 {
473 assert( head < G->nodes );
474
475 entry[used] = head;
476 order[head] = used;
477
478 dijkstraSiftUp(entry, dist, order, used);
479 ++used;
480 }
481 else
482 {
483 dijkstraSiftUp(entry, dist, order, order[head]);
484 }
485 assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
486
487 ++iters;
488 }
489 }
490 }
491 assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
492
493 return iters;
494 }
495
496
497 /** Dijkstra's algorithm for shortest paths between a pair of nodes ignoring nodes, using binary heaps, and truncated at cutoff */
dijkstraPairCutoffIgnore(const DIJKSTRA_GRAPH * G,unsigned int source,unsigned int target,unsigned int * ignore,unsigned long long cutoff,unsigned long long * dist,unsigned int * pred,unsigned int * entry,unsigned int * order)498 unsigned int dijkstraPairCutoffIgnore(
499 const DIJKSTRA_GRAPH* G, /**< directed graph */
500 unsigned int source, /**< source node */
501 unsigned int target, /**< target node */
502 unsigned int* ignore, /**< marking nodes to be ignored (if value is nonzero) */
503 unsigned long long cutoff, /**< if the distance of a node reached this value, we truncate the search */
504 unsigned long long* dist, /**< node distances (allocated by user) */
505 unsigned int* pred, /**< node predecessors in final shortest path tree (allocated by user) */
506 unsigned int* entry, /**< temporary storage (for each node - must be allocated by user) */
507 unsigned int* order /**< temporary storage (for each node - must be allocated by user) */
508 )
509 {
510 unsigned long long weight;
511 unsigned int iters = 0;
512 unsigned int used = 0;
513 unsigned int head;
514 unsigned int tail;
515 unsigned int i;
516 unsigned int e;
517
518 assert( dijkstraGraphIsValid(G) );
519 assert( source < G->nodes );
520 assert( target < G->nodes );
521 assert( dist != NULL );
522 assert( pred != NULL );
523 assert( ignore[source] == 0 );
524 assert( ignore[target] == 0 );
525
526 assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
527
528 /* initialize nodes */
529 for (i = 0; i < G->nodes; ++i)
530 {
531 dist[i] = DIJKSTRA_FARAWAY;
532 order[i] = DIJKSTRA_UNUSED;
533 pred[i] = DIJKSTRA_UNUSED;
534 }
535
536 /* enter source node into heap */
537 entry[0] = source;
538 order[source] = 0;
539 pred[source] = DIJKSTRA_UNUSED;
540 dist[source] = 0;
541
542 ++used;
543
544 /* loop while heap is not empty */
545 while ( used > 0 )
546 {
547 /* get next node */
548 tail = entry[0];
549
550 /* stop if we have found the target node */
551 if ( tail == target )
552 break;
553
554 /* remove node from heap */
555 --used;
556 entry[0] = entry[used];
557 order[entry[0]] = 0;
558 order[tail] = DIJKSTRA_UNUSED;
559
560 dijkstraSiftDown(entry, dist, order, used, 0);
561
562 assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
563 assert( entry[used] < G->nodes );
564
565 /* only work on nodes if their distance is less than the cutoff */
566 if ( dist[tail] >= cutoff )
567 continue;
568
569 /* check adjacent nodes */
570 for (e = G->outbeg[tail]; G->head[e] != DIJKSTRA_UNUSED; ++e)
571 {
572 head = G->head[e];
573
574 /* skip ignored nodes */
575 if ( ignore[head] != 0 )
576 continue;
577
578 weight = G->weight[e] + dist[tail];
579
580 /* Can we improve the current shortest path? */
581 if ( dist[head] > weight )
582 {
583 assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
584 assert( used < G->nodes );
585 assert( head <= G->nodes );
586
587 pred[head] = tail;
588 dist[head] = weight;
589
590 if ( order[head] == DIJKSTRA_UNUSED )
591 {
592 assert( head < G->nodes );
593
594 entry[used] = head;
595 order[head] = used;
596
597 dijkstraSiftUp(entry, dist, order, used);
598 ++used;
599 }
600 else
601 {
602 dijkstraSiftUp(entry, dist, order, order[head]);
603 }
604 assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
605
606 ++iters;
607 }
608 }
609 }
610 assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
611
612 return iters;
613 }
614