Skip to content

order of endpoints of edges in yen_k_shortest_simple_paths algorithm. #40878

@kappybar

Description

@kappybar

In the first test of sage.graphs.path_enumeration.yen_k_shortest_simple_paths , the following resut appears.

from sage.graphs.path_enumeration import yen_k_shortest_simple_paths
sage: g = Graph([(1, 2, 1), (2, 3, 1), (3, 4, 1), (4, 5, 2),
....:            (5, 6, 100), (4, 7, 3), (7, 6, 4), (3, 8, 5),
....:            (8, 9, 2), (9, 6, 2), (9, 10, 7), (9, 11, 10),
....:            (11, 6, 8), (10, 6, 2)])
sage: list(yen_k_shortest_simple_paths(g, 1, 6, report_edges=True, labels=True, by_weight=True))
[[(1, 2, 1), (2, 3, 1), (3, 4, 1), (4, 7, 3), (6, 7, 4)],
...

I don't think the last edge being (6, 7, 4) is intuitive. In considering the order of edges and consistency of results of other shortest simple path algorithms, (7, 6, 4) will be better. This fix is easy. Thus if it is ok, I will fix it.

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions