Skip to content

Support distance cutoff in Dijkstra shortest-path searches #1674

Description

What is the expected enhancement?

It would be useful to support an optional distance cutoff for Dijkstra shortest-path-length APIs, similar to NetworkX's single_source_dijkstra_path_length:

nx.single_source_dijkstra_path_length(
    graph,
    source,
    cutoff=10.0,
    weight="weight",
)

For example:

rustworkx.dijkstra_shortest_path_lengths(
    graph,
    source,
    edge_cost_fn,
    cutoff=10.0,
)

The main motivation is performance.

Currently, bounded Dijkstra search can be implemented with dijkstra_search() and a custom DijkstraVisitor, but this requires user-side code and Python callbacks during traversal.

A native cutoff in the Rust implementation could terminate the search once the minimum queued distance exceeds the cutoff, avoiding unnecessary heap operations and edge relaxations.

This would also make migration from NetworkX easier for workloads that rely on cutoff.

Activity

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

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions