Function shortest_path 

pub fn shortest_path<W, F, M>(fst: &F, config: ShortestPathConfig) -> Result<M>
where
    W: NaturallyOrderedSemiring,
    F: Fst<W>,
    M: MutableFst<W> + Default,

Find k-shortest paths using Yen’s algorithm

Computes the k shortest loopless paths from the start state to any final state in the FST using Yen’s algorithm. Returns an FST containing all k paths.

Algorithm: Yen’s K-Shortest Paths

Algorithm Details:

• Base: Iterative Dijkstra with edge removal
• Time Complexity: O(k × |V| × (|E| + |V| log |V|))
• Space Complexity: O(k × |V| + |V|²)
• Path Property: All returned paths are loopless (no repeated states)
• Ordering: Paths returned in strictly increasing weight order

Algorithm Steps:

1. Find the shortest path using Dijkstra
2. For each subsequent path k = 2..n:
   • For each node in path k-1:
     • Temporarily remove edges that would duplicate previous paths
     • Find shortest path from that node (spur node) to any final state
     • Add candidate path to priority queue
   • Select best candidate as path k
3. Build result FST containing all k paths

Semiring Requirements

The input FST must use a NaturallyOrderedSemiring that provides:

• Total ordering for path weight comparison
• Monotonic path weight accumulation
• Well-defined shortest path semantics

Configuration

• nshortest: Number of shortest paths to find (default: 1)
• unique: If true, only return paths with unique input/output sequences (default: false)

Examples

Single Shortest Path

use arcweight::prelude::*;

// Create FST: 0 --a/0.5--> 1 --b/0.3--> 2(final)
let mut fst = VectorFst::<TropicalWeight>::new();
let s0 = fst.add_state();
let s1 = fst.add_state();
let s2 = fst.add_state();

fst.set_start(s0);
fst.set_final(s2, TropicalWeight::one());
fst.add_arc(s0, Arc::new('a' as u32, 'a' as u32, TropicalWeight::new(0.5), s1));
fst.add_arc(s1, Arc::new('b' as u32, 'b' as u32, TropicalWeight::new(0.3), s2));

// Find single shortest path
let config = ShortestPathConfig::default();
let shortest: VectorFst<TropicalWeight> = shortest_path(&fst, config)?;

// Result contains path "ab" with total weight 0.8
assert!(shortest.num_states() > 0);

K-Best Paths

use arcweight::prelude::*;

// FST with multiple paths of different costs
let mut fst = VectorFst::<TropicalWeight>::new();
let s0 = fst.add_state();
let s1 = fst.add_state();
fst.set_start(s0);
fst.set_final(s1, TropicalWeight::one());

// Add multiple arcs with different weights
fst.add_arc(s0, Arc::new('a' as u32, 'a' as u32, TropicalWeight::new(1.0), s1));
fst.add_arc(s0, Arc::new('b' as u32, 'b' as u32, TropicalWeight::new(2.0), s1));
fst.add_arc(s0, Arc::new('c' as u32, 'c' as u32, TropicalWeight::new(3.0), s1));

// Find top 3 shortest paths
let config = ShortestPathConfig {
    nshortest: 3,
    unique: false,
};

let k_best: VectorFst<TropicalWeight> = shortest_path(&fst, config)?;
// Result FST contains all 3 paths: a (1.0), b (2.0), c (3.0)

Unique Paths Only

use arcweight::prelude::*;

let mut fst = VectorFst::<TropicalWeight>::new();
let s0 = fst.add_state();
let s1 = fst.add_state();
let s2 = fst.add_state();
fst.set_start(s0);
fst.set_final(s2, TropicalWeight::one());

// Two paths with same input/output but different intermediate states
fst.add_arc(s0, Arc::new(1, 1, TropicalWeight::new(1.0), s1));
fst.add_arc(s1, Arc::new(2, 2, TropicalWeight::new(1.0), s2));

fst.add_arc(s0, Arc::new(1, 1, TropicalWeight::new(0.5), s2)); // Direct path, same I/O

// Find unique paths only
let config = ShortestPathConfig {
    nshortest: 5,
    unique: true,  // Filter duplicate input/output sequences
};

let unique_paths: VectorFst<TropicalWeight> = shortest_path(&fst, config)?;

Complex Network

use arcweight::prelude::*;

// Complex FST with multiple paths through different routes
let mut fst = VectorFst::<TropicalWeight>::new();
let s0 = fst.add_state();
let s1 = fst.add_state();
let s2 = fst.add_state();
let s3 = fst.add_state();
let s4 = fst.add_state();

fst.set_start(s0);
fst.set_final(s4, TropicalWeight::one());

// Create diamond pattern with multiple paths
fst.add_arc(s0, Arc::new(1, 1, TropicalWeight::new(1.0), s1)); // Top route
fst.add_arc(s1, Arc::new(2, 2, TropicalWeight::new(1.0), s3));
fst.add_arc(s3, Arc::new(3, 3, TropicalWeight::new(1.0), s4));

fst.add_arc(s0, Arc::new(4, 4, TropicalWeight::new(2.0), s2)); // Bottom route
fst.add_arc(s2, Arc::new(5, 5, TropicalWeight::new(1.0), s3));
fst.add_arc(s3, Arc::new(3, 3, TropicalWeight::new(1.0), s4));

// Find 10 best paths
let config = ShortestPathConfig {
    nshortest: 10,
    unique: false,
};

let paths: VectorFst<TropicalWeight> = shortest_path(&fst, config)?;

Performance Characteristics

• Time per path: O(|V| × (|E| + |V| log |V|))
• Total time: O(k × |V| × (|E| + |V| log |V|))
• Memory: O(k × |V|) for storing k paths + O(|V|²) for edge exclusion tracking
• Optimality: Guaranteed to find k shortest loopless paths in order

Errors

Returns Error::Algorithm if:

• The input FST has no start state
• No paths exist to any final state
• Memory allocation fails during computation
• Weight computation overflows or becomes infinite

References

[1] Yen, J. Y. 1971. Finding the k shortest loopless paths in a network. Management Science 17, 11 (July 1971), 712-716. DOI: https://doi.org/10.1287/mnsc.17.11.712

[2] Mohri, M. and Riley, M. 2002. An efficient algorithm for the n-best-strings problem. In Proceedings of ICSLP 2002, 1313-1316.

See Also

• shortest_path_single - Convenience function for single shortest path
• shortest_distance - Compute path weight sums
• NaturallyOrderedSemiring - Required trait

Examples found in repository

examples/string_alignment.rs (line 317)

fn compute_alignment_fst(source: &str, target: &str) -> Result<Alignment> {
    // Build alignment FST
    let alignment_fst = build_alignment_fst(source, target, 1.0, 1.0, 1.0);

    // Find shortest path
    let shortest = shortest_path(&alignment_fst, ShortestPathConfig::default())?;

    // Extract alignment from shortest path
    extract_alignment_from_path(source, target, &shortest)
}

examples/edit_distance.rs (line 135)

fn compute_edit_distance(
    source: &str,
    target: &str,
    insertion_cost: f32,
    deletion_cost: f32,
    substitution_cost: f32,
) -> Result<f32> {
    // Build edit distance FST that directly computes the distance
    let edit_fst = build_edit_distance_fst(
        source,
        target,
        insertion_cost,
        deletion_cost,
        substitution_cost,
    );

    // Find shortest path from start to final state
    let config = ShortestPathConfig::default();
    let shortest: VectorFst<TropicalWeight> = shortest_path(&edit_fst, config)?;

    // Get the cost from the shortest path
    if let Some(start) = shortest.start() {
        // Check if there's a path to a final state
        let mut stack = vec![(start, 0.0)];
        let mut visited = std::collections::HashSet::new();

        while let Some((state, cost)) = stack.pop() {
            if visited.contains(&state) {
                continue;
            }
            visited.insert(state);

            if shortest.is_final(state) {
                return Ok(cost);
            }

            for arc in shortest.arcs(state) {
                stack.push((arc.nextstate, cost + arc.weight.value()));
            }
        }
    }

    // If no path found, return infinity
    Ok(f32::INFINITY)
}

examples/spell_checking.rs (line 211)

fn find_spelling_corrections(
    dict_fst: &VectorFst<TropicalWeight>,
    target: &str,
    max_distance: usize,
) -> Result<Vec<(String, f32)>> {
    // Build edit distance FST
    let edit_fst = build_edit_distance_fst(target, max_distance);

    // Compose dictionary with edit distance FST
    let composed: VectorFst<TropicalWeight> = compose_default(dict_fst, &edit_fst)?;

    // Find shortest paths
    let config = ShortestPathConfig {
        nshortest: 10,
        ..Default::default()
    };
    let shortest: VectorFst<TropicalWeight> = shortest_path(&composed, config)?;

    // Extract words and distances
    let mut results = Vec::new();

    if let Some(start) = shortest.start() {
        extract_paths(&shortest, start, &mut Vec::new(), 0.0, &mut results);
    }

    // Deduplicate results and keep the best score for each word
    let mut word_scores: HashMap<String, f32> = HashMap::new();
    for (word, score) in results {
        word_scores
            .entry(word)
            .and_modify(|e| *e = e.min(score))
            .or_insert(score);
    }

    // Convert back to vec and sort by distance
    let mut final_results: Vec<(String, f32)> = word_scores.into_iter().collect();
    final_results.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap());
    Ok(final_results)
}