Module traitgraph::algo::dijkstra [−][src]
Expand description
Dijkstra’s shortest path algorithm.
Structs
Data structure for Dijkstra’s shortest path algorithm.
An epoch counter array. This can be used to check if an index is current by comparing its entry in the epoch array to the current epoch. To unmark all values, the current epoch can be increased in O(1). Only overflows have to be handled by resetting all epoch counters.
An epoched node weight array that can be cleared in O(1) most of the times. Only if the epoch in the epoch array overflows, clearing takes linear time.
Traits
A data structure that decides whether a given node index is a target of the current Dijkstra search.
An array to store minimal node weights for Dijkstra’s algorithm.
A weight-type usable in Dijkstra’s algorithm.
Edge data that has a weight usable for shortest path computation.
Type Definitions
A Dijkstra implementation with a set of common optimisations.