Path Selection (Predecessor Selection)
The shortest path calculation generates a predecessor list for each vertex. If this list defines more than one path, generating the entire list of shortest paths requires more (possibly exponential) time and memory. There are two ways to increase efficiency.
- To select an arbitrary single shortest-path, use the following call instead of
prg_djk_path_get():
prg_djk_ path_get_options (..., ..., PRGC_DJK_PATH_GET_OPT_FIRST_FOUND)
- To select a client-defined single shortest path, define a
PrgT_Djk_Predecessor_Selection_Procand register it usingprg_djk_predecessor_selection_proc_register(). As a shortest path is built (backwards from the destination to the source), this function will be called to choose among the equal-cost predecessor vertices.