Note that Dijkstra's algorithm is exact; no beam search is required as in some neural sequence models.
,ŷ may not be the most probable string-extracting that from a weighted FST is NP-hard (Casacuberta and de la Higuera, 1999).