Scippy

SCIP

Solving Constraint Integer Programs

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