Two Algorithms for Finding $k$ Shortest Paths of a Weighted Pushdown Automaton

Ke Wu, Philip Resnik

We introduce efficient algorithms for finding the $k$ shortest paths of a weighted pushdown automaton (WPDA), a compact representation of a weighted set of strings with potential a…