Shortest-Distance Problems and Algorithms

Description

Shortest-distance problems arise in a variety of applications.

General Shortest-Distance Problems: Traditional single-source or all-pair shortest-distance problems were introduced in the tropical semiring ((min,+)-semiring). These problems can be generalized to the case of an arbitrary semiring. There exists a simple and generic single-source shortest-distance algorithm that works with any k-closed semiring and that is correct regardless of the queue discipline chosen for its implementation. Classical algorithms such as those of Bellman-Ford, Dijkstra, or Lawler, are all specific instances of that generic algorithm. The classical all-pairs shortest-distance algorithm of Floyd-Warshall can also be straight-forwardedly generalized to the case of closed semirings, non-necessarily idempotent.
n-Best-Strings Problems: The problem of determining the n shortest paths of a weighted directed graph is a well-studied problem and admits a large number of variants. The related problems that arise in text and speech processing applications are different. The weighted graphs considered in such applications are weighted automata and it is often desirable to determine not the n best paths, but the n best distinct strings of the automaton with the lowest costs.

Related Publications

Mehryar Mohri.
Semiring Frameworks and Algorithms for Shortest-Distance Problems.
Journal of Automata, Languages and Combinatorics, 7(3):321-350, 2002.

Mehryar Mohri and Michael Riley.
An Efficient Algorithm for the N-Best-Strings Problem.
In Proceedings of the International Conference on Spoken Language Processing 2002 (ICSLP '02). Denver, Colorado, September 2002.

Mehryar Mohri.
General Algebraic Frameworks and Algorithms for Shortest-Distance Problems. Technical Memorandum 981210-10TM, AT&T Labs - Research, 62 pages, 1998.