Clarify that `dijkstra_search` is not a multi-source BFS

[tsondru]

Information

• rustworkx-core version: 0.18.0 (crates.io)
• Rust version: stable
• Operating system: Linux

What is happening?

rustworkx_core::traversal::dijkstra_search accepts an iterator of start nodes, but the docs only say "Starting points are the nodes in the iterator starts" and the doc-comment pseudocode describes a single source s. What multiple starts actually do is left unspecified — and the actual behavior is surprising.

Actual behavior (traversal/dijkstra_visit.rs:180-207 at the 0.18.0 tag): starts are processed sequentially, each with a fresh local scores/heap but a shared visited map. Node processing is gated by !visited.visit(node) and edge relaxation by visited.is_visited(&next) — so once an earlier start finalizes a node, later starts can never relax into it, even with a strictly smaller distance. The result is an order-dependent partition ("first start in iteration order to finalize a node wins it"), not the min-distance-from-any-source semantics that BGL's dijkstra visitor and NetworkX's multi_source_dijkstra provide via joint queue seeding.

The same sequential-restart pattern exists in bfs_search/dfs_search, where it is a reasonable "forest" semantics because those events carry no costs. dijkstra_search is different: Discover/EdgeRelaxed events carry costs, so a caller who reads them as shortest distances gets silently order-dependent answers whenever the reachable sets of different starts overlap.

How can we reproduce the issue?

Verified against crates.io rustworkx-core = "0.18.0":

use rustworkx_core::petgraph::graph::{node_index as n, DiGraph};
use rustworkx_core::traversal::{dijkstra_search, DijkstraEvent};

// A -> X (weight 10), B -> X (weight 1)
let mut g: DiGraph<(), u32> = DiGraph::new();
let (a, b, x) = (g.add_node(()), g.add_node(()), g.add_node(()));
g.add_edge(a, x, 10);
g.add_edge(b, x, 1);

let run = |starts: Vec<_>| {
    let mut cost_of_x = None;
    dijkstra_search(&g, starts, |e| Ok::<u32, ()>(*e.weight()), |event| {
        if let DijkstraEvent::Discover(v, cost) = event {
            if v == x { cost_of_x = Some(cost); }
        }
        Ok::<(), ()>(())
    }).unwrap();
    cost_of_x.unwrap()
};

assert_eq!(run(vec![n(0), n(1)]), 10); // starts [A, B]: X discovered at cost 10 (via A — stale)
assert_eq!(run(vec![n(1), n(0)]), 1);  // starts [B, A]: X discovered at cost 1 (the true minimum)

Same graph, same query — the reported cost of X depends purely on start-list order. A true multi-source Dijkstra would report 1 in both cases.

What should happen?

Preferably: seed all starts into a single priority queue at distance zero (the BGL / NetworkX multi_source_dijkstra semantics), so Discover(v, cost) always carries the minimum distance from the nearest start regardless of iteration order. If changing the existing function's behavior is considered too breaking, a separate multi_source_dijkstra_search entry point would serve the same need.

Failing that, at minimum: document the sequential shared-visited semantics explicitly and warn that multi-start is not multi-source shortest path (current workaround: call per-start and take the per-node min).

Happy to help with a PR for whichever direction the maintainers prefer.

[IvanIsCoding]

https://www.rustworkx.org/apiref/rustworkx.dijkstra_search.html has better documentation. While the current signature can be misleading, the current implementation behaviour is working as intended. The forest behaviour that currently exists was intentional, it is directly copied from DFS/BFS traversals. I am pretty sure the Python tests validate it.

Your reproduction snippet is using the function incorrectly. rustworkx-core does not currently have any multi-source methods. We would accept a PR implementing an equivalent to Networkx's multi-source Dijkstra. But retrofitting new behaviour in that function is not the solution.

We can add multi_source_dijkstra_shortest_paths, multi_source_dijkstra_shortest_paths_lenghts, and multi_source_dijkstra_search and document what starts means for the current method. That is the way forward. If you send a PR changing the current behavior, it will be rejected.

[IvanIsCoding]

And if you urgently need multi_source_dijkstra_search, add the auxiliary node connected with your sources with edges of weight zero. That should work, of course it's more work than a built-in method but at least it gets you somewhere without reimplementing the logic.

[tsondru]

Thanks — that's a clear answer, and the forest framing makes sense once it's stated as the shared starts contract with breadth_first_search/depth_first_search. Happy to leave dijkstra_search alone; I won't send anything that changes its behaviour.

I'd like to pick up the new functions. Two questions before I start.

1. rustworkx-core only, or the Python layer too?

• Core only — multi_source_dijkstra_shortest_paths, multi_source_dijkstra_shortest_path_lengths, and multi_source_dijkstra_search in rustworkx-core, following the existing DistanceMap / Measure / fallible-edge_cost conventions, with the same doc-example + unit-test style as the surrounding modules.
• Core + bindings — the above plus the graph_* / digraph_* pairs in src/shortest_path/mod.rs, .pyi stubs, API docs, and a release note.

I'm happy to do the full stack, but it's a much bigger diff to review, so I'd rather land core first and follow up with bindings in a second PR if that suits your review bandwidth. Let me know which you prefer.

2. Event semantics for multi_source_dijkstra_search.

The two shortest-path functions are a straightforward generalisation of the seeding block in dijkstra.rs — push every start at K::default() instead of one. The visitor variant is the only place with a real design decision, since DijkstraEvent has to say something about the sources themselves. With all sources seeded at zero:

• Does each source get its own Discover(s, K::default()) as it pops, or should seeds be silent?
• An edge between two sources can never relax (both are already final at zero under non-negative weights), so it would surface as EdgeNotRelaxed. Intended, or should inter-source edges be suppressed?
• A visitor recording predecessors on EdgeRelaxed — the pattern in the current doc example — gets a shortest-path forest with |sources| roots rather than a single tree. Worth calling out in the docs.

The tidiest spec I can think of is "exactly the event stream you would get from the auxiliary-super-source construction, minus the artificial node and its zero-weight edges." That answers all three consistently: seeds do fire Discover(s, 0), inter-source edges do fire EdgeNotRelaxed, and the forest shape is inherent. Happy to go with that unless you'd rather define it differently.

I'll also include the docs clarification for what starts means on the existing dijkstra_search (and the equivalent note on the Python side if bindings are in scope), since that's useful regardless.

Small naming note: I'll go with multi_source_dijkstra_shortest_path_lengths — singular "path" — to match the existing dijkstra_shortest_path_lengths / graph_dijkstra_shortest_path_lengths. Say the word if you'd rather have the plural.

One more thing worth recording for anyone who lands here from a search: the auxiliary-super-source trick works well as an interim workaround. Adding one node joined to every source by a zero-weight edge and then running single-start dijkstra_search gives the true multi-source minimum, and unlike per-start-plus-manual-min it stays a single traversal. I've verified it against the a ->(10) x, b ->(1) x case from the original report — it reports 1 regardless of the order the sources are attached in.

[IvanIsCoding]

Send me the bare minimum amount of functional code in rustworkx-core. Do not send the Python bindings in the same PR, that can be done in a separate follow up PR.

Because you'll only contribute to rustworkx-core, don't worry about path_lengths, paths, etc. Make a new file src/shortest_path/multi_source_dijkstra.rs. My initial recommendation for multi_source_dijkstra is to create a graph with the virtual source connected to all sources in the input with weight zero. Then you call dijkstra and filter all edges with the virtual source to the existing nodes. Add separate tests for multi_source_dijkstra method in that same file in the same style. Make sure to include a test case where goal is one of the sources in your input. And a test case for when you provide an empty list of sources.

For multi_source_dikstra_search, don't rewrite the existing search code. Reuse the code from rustworkx-core/src/traversal/dijkstra_visit.rs in a new file rustworkx-core/src/traversal/multi_source_dijkstra_visit.rs. Make each node have Discover(s, K::default()), make it fire EdgeNotRelaxed for the edges between sources. For this case, the multi_source_dijkstra_search should reuse the dijkstra_search implementation. Create a virtual source, add it to the graph with the zero edges, forward events from dijkstra_search filtering any event involving the virtual source.

For both strategies, you'll need to either clone the graph or make a clever shallow copy of the input to add the virtual source. I do not care too much about which one you pick. Just submit something maintainable.

I will also make you very clear that if you violate my suggestions and go editing rustworkx_core::shortest_path::dijkstra or rustworkx_core::traversal::dijkstra_search, I will reject your PR. Show your best work and that you care about existing users of the library. The current code works for many, build on top of it.

[shayaanzari]

Hi Ivan Carvalho (@IvanIsCoding), is this currently being worked on? If not, I'd like to implement the new functions and test cases without touching the existing traversal code, following the architecture you described.

[IvanIsCoding]

Hi @IvanIsCoding, is this currently being worked on? If not, I'd like to implement the new functions and test cases without touching the existing traversal code, following the architecture you described.

This is not being worked on, you can submit a PR if you want