Template Function ADS::isShortestPathTree

• Defined in File ShortestPaths.h

Function Documentation

template<Graph G>
bool ADS::isShortestPathTree(const G &g, int r, const ShortestPathTree<typename G::Weight> &R)

whether R is a tree of shortest paths from r: d[ r ] = 0, the unreachable nodes at infinity() with no parent, d[ v ] = d[ T[ v ] ] + w( T[ v ] , v ) on the others, and d[ u ] + w( u , v ) >= d[ v ] on each edge from a reached node (the Teorema 11.1), O( n + m ) on lists