Scippy

SCIP

Solving Constraint Integer Programs

dijkstra.h File Reference

Detailed Description

Definitions for Disjkstra's shortest path algorithm.

Author
Thorsten Koch
Marc Pfetsch

Definition in file dijkstra.h.

Go to the source code of this file.

Data Structures

struct  DIJKSTRA_Graph
 

Macros

#define DIJKSTRA_Bool   unsigned int
 
#define TRUE   1
 
#define FALSE   0
 
#define DIJKSTRA_FARAWAY   0xffffffffu
 
#define DIJKSTRA_UNUSED   0xffffffffu
 

Typedefs

typedef struct DIJKSTRA_Graph DIJKSTRA_GRAPH
 

Functions

DIJKSTRA_Bool dijkstraGraphIsValid (const DIJKSTRA_GRAPH *G)
 
unsigned int dijkstra (const DIJKSTRA_GRAPH *G, unsigned int source, unsigned long long *dist, unsigned int *pred, unsigned int *entry, unsigned int *order)
 
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 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)
 
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)
 

Macro Definition Documentation

◆ DIJKSTRA_Bool

#define DIJKSTRA_Bool   unsigned int

type used for boolean values

Definition at line 31 of file dijkstra.h.

◆ TRUE

#define TRUE   1

boolean value TRUE

Definition at line 34 of file dijkstra.h.

◆ FALSE

#define FALSE   0

boolean value FALSE

Definition at line 35 of file dijkstra.h.

◆ DIJKSTRA_FARAWAY

#define DIJKSTRA_FARAWAY   0xffffffffu

node has distance 'infinity'

Definition at line 38 of file dijkstra.h.

Referenced by dijkstra(), dijkstraPair(), dijkstraPairCutoff(), dijkstraPairCutoffIgnore(), and separateGLS().

◆ DIJKSTRA_UNUSED

#define DIJKSTRA_UNUSED   0xffffffffu

Typedef Documentation

◆ DIJKSTRA_GRAPH

graph structure - use consecutive storage for arcs

Definition at line 56 of file dijkstra.h.

Function Documentation

◆ dijkstraGraphIsValid()

DIJKSTRA_Bool dijkstraGraphIsValid ( const DIJKSTRA_GRAPH G)

◆ dijkstra()

unsigned int dijkstra ( const DIJKSTRA_GRAPH G,
unsigned int  source,
unsigned long long *  dist,
unsigned int *  pred,
unsigned int *  entry,
unsigned int *  order 
)

Dijkstra's algorithm using binary heaps

Dijkstra's algorithm for shortest paths from a single source using binary heaps

Parameters
Gdirected graph
sourcesource node
distnode distances (allocated by user)
prednode predecessors in final shortest path tree (allocated by user)
entrytemporary storage (for each node - must be allocated by user)
ordertemporary storage (for each node - must be allocated by user)

Definition at line 180 of file dijkstra.c.

References DIJKSTRA_FARAWAY, DIJKSTRA_UNUSED, dijkstraGraphIsValid(), dijkstraHeapIsValid(), dijkstraSiftDown(), dijkstraSiftUp(), DIJKSTRA_Graph::head, DIJKSTRA_Graph::nodes, NULL, DIJKSTRA_Graph::outbeg, BMS_BufMem::used, and DIJKSTRA_Graph::weight.

◆ 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 
)

Dijkstra's algorithm for shortest paths between a pair of nodes using binary heaps

Parameters
Gdirected graph
sourcesource node
targettarget node
distnode distances (allocated by user)
prednode predecessors in final shortest path tree (allocated by user)
entrytemporary storage (for each node - must be allocated by user)
ordertemporary storage (for each node - must be allocated by user)

Definition at line 280 of file dijkstra.c.

References DIJKSTRA_FARAWAY, DIJKSTRA_UNUSED, dijkstraGraphIsValid(), dijkstraHeapIsValid(), dijkstraSiftDown(), dijkstraSiftUp(), DIJKSTRA_Graph::head, DIJKSTRA_Graph::nodes, NULL, DIJKSTRA_Graph::outbeg, BMS_BufMem::used, and DIJKSTRA_Graph::weight.

◆ 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 
)

Dijkstra's algorithm for shortest paths between a pair of nodes using binary heaps and truncated at cutoff

Parameters
Gdirected graph
sourcesource node
targettarget node
cutoffif the distance of a node reached this value, we truncate the search
distnode distances (allocated by user)
prednode predecessors in final shortest path tree (allocated by user)
entrytemporary storage (for each node - must be allocated by user)
ordertemporary storage (for each node - must be allocated by user)

Definition at line 386 of file dijkstra.c.

References DIJKSTRA_FARAWAY, DIJKSTRA_UNUSED, dijkstraGraphIsValid(), dijkstraHeapIsValid(), dijkstraSiftDown(), dijkstraSiftUp(), DIJKSTRA_Graph::head, DIJKSTRA_Graph::nodes, NULL, DIJKSTRA_Graph::outbeg, BMS_BufMem::used, and DIJKSTRA_Graph::weight.

Referenced by separateGLS().

◆ 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 
)

Dijkstra's algorithm for shortest paths between a pair of nodes ignoring nodes, using binary heaps, and truncated at cutoff

Parameters
Gdirected graph
sourcesource node
targettarget node
ignoremarking nodes to be ignored (if value is nonzero)
cutoffif the distance of a node reached this value, we truncate the search
distnode distances (allocated by user)
prednode predecessors in final shortest path tree (allocated by user)
entrytemporary storage (for each node - must be allocated by user)
ordertemporary storage (for each node - must be allocated by user)

Definition at line 497 of file dijkstra.c.

References DIJKSTRA_FARAWAY, DIJKSTRA_UNUSED, dijkstraGraphIsValid(), dijkstraHeapIsValid(), dijkstraSiftDown(), dijkstraSiftUp(), DIJKSTRA_Graph::head, DIJKSTRA_Graph::nodes, NULL, DIJKSTRA_Graph::outbeg, BMS_BufMem::used, and DIJKSTRA_Graph::weight.

Referenced by separateGLS().