46 unsigned int count = 0;
70 if ( count > G->
arcs )
84 const unsigned int* entry,
85 const unsigned long long* value,
86 const unsigned int* order,
87 const unsigned int used,
88 const unsigned int size
93 if ( entry ==
NULL || value ==
NULL || order ==
NULL || used > size )
97 for (
i = 0;
i < used / 2; ++
i)
99 if ( value[entry[
i]] > value[entry[
i +
i]] )
101 if (
i +
i + 1 < used && value[entry[
i]] > value[entry[
i +
i + 1]] )
114 const unsigned long long* value,
120 unsigned long long val;
125 child = current + current;
126 ent = entry[current];
129 while ( child < used )
133 if ( child + 1 < used )
135 if ( value[entry[child + 1]] < value[e] )
141 if ( value[e] >= val )
150 entry[current] = ent;
151 order[ent] = current;
159 const unsigned long long* value,
164 unsigned long long val;
169 ent = entry[current];
172 while ( current > 0 )
174 parent = current / 2;
177 if ( value[e] <= val )
184 entry[current] = ent;
185 order[ent] = current;
193 unsigned long long* dist,
199 unsigned long long weight;
200 unsigned int iters = 0;
201 unsigned int used = 0;
208 assert( source < G->nodes );
238 entry[0] = entry[used];
251 weight = G->
weight[e] + dist[tail];
254 if ( dist[head] > weight )
257 assert( used < G->nodes );
258 assert( head <= G->nodes );
265 assert( head < G->nodes );
294 unsigned long long* dist,
300 unsigned long long weight;
301 unsigned int iters = 0;
302 unsigned int used = 0;
309 assert( source < G->nodes );
310 assert( target < G->nodes );
339 if ( tail == target )
344 entry[0] = entry[used];
357 weight = G->
weight[e] + dist[tail];
360 if ( dist[head] > weight )
363 assert( used < G->nodes );
364 assert( head <= G->nodes );
371 assert( head < G->nodes );
400 unsigned long long cutoff,
401 unsigned long long* dist,
407 unsigned long long weight;
408 unsigned int iters = 0;
409 unsigned int used = 0;
416 assert( source < G->nodes );
417 assert( target < G->nodes );
446 if ( tail == target )
451 entry[0] = entry[used];
461 if ( dist[tail] >=
cutoff )
468 weight = G->
weight[e] + dist[tail];
471 if ( dist[head] > weight )
474 assert( used < G->nodes );
475 assert( head <= G->nodes );
482 assert( head < G->nodes );
511 unsigned int* ignore,
512 unsigned long long cutoff,
513 unsigned long long* dist,
519 unsigned long long weight;
520 unsigned int iters = 0;
521 unsigned int used = 0;
528 assert( source < G->nodes );
529 assert( target < G->nodes );
532 assert( ignore[source] == 0 );
533 assert( ignore[target] == 0 );
560 if ( tail == target )
565 entry[0] = entry[used];
575 if ( dist[tail] >=
cutoff )
584 if ( ignore[head] != 0 )
587 weight = G->
weight[e] + dist[tail];
590 if ( dist[head] > weight )
593 assert( used < G->nodes );
594 assert( head <= G->nodes );
601 assert( head < G->nodes );
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)
unsigned int dijkstra(const DIJKSTRA_GRAPH *G, unsigned int source, unsigned long long *dist, unsigned int *pred, unsigned int *entry, unsigned int *order)
static void dijkstraSiftUp(unsigned int *entry, const unsigned long long *value, unsigned int *order, unsigned int current)
static void dijkstraSiftDown(unsigned int *entry, const unsigned long long *value, unsigned int *order, unsigned int used, unsigned int current)
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)
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)
DIJKSTRA_Bool dijkstraGraphIsValid(const DIJKSTRA_GRAPH *G)
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)
Definitions for Disjkstra's shortest path algorithm.
struct DIJKSTRA_Graph DIJKSTRA_GRAPH
assert(minobj< SCIPgetCutoffbound(scip))