Data Structures
The DJK package augments a prg_graph structure with data needed to compute and efficiently cache information related to shortest paths. This data is generally only accessible through the DJK API, and includes:
- Graph cache—a description of the graph that is inconvenient for altering graph structure, but efficient for performing calculations on the graph. Enabling the graph cache speeds up repeated shortest-path computations. The graph cache is valid until an edge or vertex is added or removed. The cache must be disabled explicitly when the graph structure changes; the DJK package does not internally track whether the cache is valid. See Utility Functions and Options for simple guidance on cache maintenance.
- Predecessor lists—a compact representation of the set of equal-cost shortest-paths from a source to all destinations. See the predecessor list definition for more details.)
- Routing tables—compact description of next-hops from one or many source vertices to all other vertices (destinations).