String[] osyms = fst.getOsyms();
while (!queue.isEmpty()) {
State s = queue.remove();
Path currentPath = paths.get(s);
if (s.getFinalWeight() != semiring.zero()) {
String pathString = currentPath.getPath().toString();
if (finalPaths.containsKey(pathString)) {
// path already exist. update its cost
Path old = finalPaths.get(pathString);
if (old.getCost() > currentPath.getCost()) {