46 unsigned int count = 0;
53 for (
i = 0;
i <
G->nodes; ++
i)
55 for (
k =
G->outbeg[
i];
k <
G->outbeg[
i] +
G->outcnt[
i]; ++
k)
57 if (
G->head[
k] >=
G->nodes )
60 if (
G->weight[
k] >
G->maxweight ||
G->weight[
k] <
G->minweight )
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
97 for (
i = 0;
i < used / 2; ++
i)
114 const unsigned long long* value,
120 unsigned long long val;
129 while ( child < used )
133 if ( child + 1 < used )
135 if ( value[
entry[child + 1]] < value[
e] )
141 if ( value[
e] >= val )
159 const unsigned long long* value,
164 unsigned long long val;
177 if ( value[
e] <= val )
193 unsigned long long* dist,
199 unsigned long long weight;
200 unsigned int iters = 0;
201 unsigned int used = 0;
215 for (
i = 0;
i <
G->nodes; ++
i)
251 weight =
G->weight[
e] + dist[
tail];
254 if ( dist[head] > weight )
294 unsigned long long* dist,
300 unsigned long long weight;
301 unsigned int iters = 0;
302 unsigned int used = 0;
317 for (
i = 0;
i <
G->nodes; ++
i)
357 weight =
G->weight[
e] + dist[
tail];
360 if ( dist[head] > weight )
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;
424 for (
i = 0;
i <
G->nodes; ++
i)
468 weight =
G->weight[
e] + dist[
tail];
471 if ( dist[head] > weight )
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;
538 for (
i = 0;
i <
G->nodes; ++
i)
587 weight =
G->weight[
e] + dist[
tail];
590 if ( dist[head] > weight )
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.
assert(minobj< SCIPgetCutoffbound(scip))