Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Yen's Algorithm cannot handle multiple edges #516

Open
HellOwhatAs opened this issue Jan 24, 2024 · 1 comment
Open

Yen's Algorithm cannot handle multiple edges #516

HellOwhatAs opened this issue Jan 24, 2024 · 1 comment

Comments

@HellOwhatAs
Copy link

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
Copy link
Collaborator

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)).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants