Skip to main content

longest_path_from

Function longest_path_from 

Source
pub fn longest_path_from(
    node: &str,
    graph: &HashMap<String, HashSet<String>>,
    visited: &mut HashSet<String>,
    memo: &mut HashMap<String, Vec<String>>,
) -> Vec<String>
Expand description

Find the longest path from a node using DFS with memoization.

§Memoization limitation

Results are cached keyed only by node. When the same node is reached from two different roots the first cached result is reused, even though the visited set differs between the two calls. This means the cached result may be shorter than what would be computed from a different root (because some successors were marked visited in the first traversal). The trade-off is acceptable: the memo avoids O(n²) worst-case work and the goal is finding representative longest paths, not an exhaustive enumeration.