Yen's Algorithm cannot handle multiple edges

[HellOwhatAs]

hello !

I noticed that the shortest path in this crate is represented using vertices Vec<N>, assuming that there are no multiple edges.

This assumption is not an issue when finding the shortest path (as it will only consider the shortest edge among multiple edges). However, for the k-shortest path problem, I believe multiple edges could lead to different scenarios.

Consider the problem of finding 2 shortest loopless paths from A to B in the following graph:

graph TD;
    A -- "edge(id: 0, cost: 3)" ----> B;
    A -- "edge(id: 1, cost: 2)" ----> B;

Loading

use pathfinding::directed::yen::yen;
let paths = yen(
    &'A',
    |c| match c {
        'A' => vec![('B', 3), ('B', 2)],
        'B' => vec![],
        _ => unreachable!()
        },
        |c| *c == 'B',
2);
println!("{:?}", paths);

Yen's Algorithm only finds one:

[(['A', 'B'], 2)]

Because currently edges are filtered by (head vertex, tail vertex).

Sadly the pseudocode on Wikipedia also does the same thing 😭.

Have I missed something / is there a simple way to solve this?

[samueltardieu]

Hi. You are right, the current edges representation does not allow edges distinction. The kind of graph that can be represented should probably be described in the documentation, or we should think of a possible backward compatible change which would allow to return ids along with edges (the default one being the couple (start, end)).