Skip to content

Add an option to specify how the next_cost is calculated in dijkstra_search? #1590

@willGraham01

Description

@willGraham01

What is the expected enhancement?

Context

In a neuroscience-based project I'm currently working on, I find myself needing to solve the widest path problem.

I looked through the API, but couldn't find a dedicated function for solving this problem. However widest-path problems can be solved with a small edit to any shortest path algorithm, and rustworkx already offers an implementation of dijkstra_search. To adapt this traversal to provide a solution to the widest-path problem, I would just need to change the following line in the pseudo-code for dijkstra_search,

next_cost = cost + weight(w)

to

next_cost = min(cost, weight(w))

However the calculation of the next_cost line is hard-coded into the method, unlike the weight_fn which can be specified by the user (which isn't surprising, since that is after all what Dijkstra's algorithm is!). I tried writing a subclass of DijkstraVisitor to get around this, but I don't think that's possible since the visitor also can't affect the next cost calculation (and thus traversal order).

Desired Feature

The "next cost calculation" could be exposed to the user through the arguments passed to dijkstra_search. For example;

dijkstra_search(graph, source, weight_fn, next_cost_fn, visitor)

which then has the affect of altering the (psuedo-code) to be

next_cost = next_cost_fn(cost, weight(w))

with next_cost_fn defaulting to the sum of the cost and weight(w) as per standard Dijkstra's algorithm.

This would mean that dijkstra_search could be used to solve widest-path problems, and more generally any other problem that just requires a slight adaptation of how the cost of a subsequent node in a path is calculated.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type
    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions