Two Algorithms for Finding $k$ Shortest Paths of a Weighted Pushdown Automaton
Ke Wu, Philip Resnik · arXiv (Cornell University) · 2012
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 applications in parsing and machine translation. Both of our algorithms are derived from the same weighted deductive logic description of the execution of a WPDA using different search strategies. Experimental results show our Algorithm 2 adds very little overhead vs. the single shortest path algorithm, even with a large $k$.