  We survey $k$-best enumeration problems and the algorithms for solving them,
including in particular the problems of finding the $k$ shortest paths, $k$
smallest spanning trees, and $k$ best matchings in weighted graphs.
