Skip to content

k shortest path does not return the shortest path when using MaxFrontierSize #9577

@hr-alebel

Description

@hr-alebel

Describe the bug

In #9333 a new Feature got introduced called MaxFrontierSize, which limits memory usage in case of high density graphs. This causes a algorithmic issue, because the "best" node is droped from the priority queue when the MaxFrontierSize is triggered.
This causes a nearly 100% to not get the shortest path ever.

To Reproduce

Steps to reproduce the behavior:

  1. run shortest path query with numpath = 1 to get the shortest path
  2. run the same query with numpath > 1 with MaxFrontierSize low enough to get triggered on your data set
  3. Compare Paths

Expected behavior

numpaths > 1 should return the somewhat shortest paths, possibly even the correct shortest paths

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions