## Brief
Add [bidirectional
Dijkstra's](https://en.wikipedia.org/wiki/Bidirectional_search)
algorithm for the shortest path between two points.
```rust
pub fn bidirectional_dijkstra<G, F, K>(
    graph: G,
    start: G::NodeId,
    goal: G::NodeId,
    mut edge_cost: F,
) -> Option<K>
where
    G: Visitable + IntoEdgesDirected,
    G::NodeId: Eq + Hash,
    F: FnMut(G::EdgeRef) -> K,
    K: Measure + Copy,
   ```

## About the algorithm and implementation
The time complexity of bi-directional dijkstra is the same as normal dijkstra. However, in certain scenarios (e.g. grids and sparse road networks), it has to explore significantly less nodes to find the shortest path. https://www.ucl.ac.uk/~ucahmto/math/2020/05/30/bidirectional-dijkstra.html is a great resource on the correctness of the algorithm.

## Benchmarks
Under the right circumstances (large & sparse networks), it clearly shows that bidirectional dijkstra is faster than normal dijkstra.
```
test dijkstra_bench_grid ... bench: 469,582.30 ns/iter (+/- 12,469.78)
test dijkstra_bench_grid_bidirectional ... bench: 47,145.54 ns/iter (+/-
1,139.01)
test dijkstra_bench_grid_with_target ... bench: 118,156.60 ns/iter (+/-
3,168.78)
```

However, the existing benchmark also shows that it's not always beneficial.
```
test dijkstra_bench_random ... bench: 745,014.06 ns/iter (+/- 22,892.76)
test dijkstra_bench_random_bidirectional ... bench: 1,556,466.68 ns/iter
(+/- 77,702.84)
test dijkstra_bench_random_with_target ... bench: 694,060.94 ns/iter
(+/- 18,275.15)
```

On macbook pro M1

---------

Co-authored-by: Raoul Luqué <125205120+RaoulLuque@users.noreply.github.com>

## Brief
Add [bidirectional
Dijkstra's](https://en.wikipedia.org/wiki/Bidirectional_search)
algorithm for the shortest path between two points.
```rust
pub fn bidirectional_dijkstra<G, F, K>(
    graph: G,
    start: G::NodeId,
    goal: G::NodeId,
    mut edge_cost: F,
) -> Option<K>
where
    G: Visitable + IntoEdgesDirected,
    G::NodeId: Eq + Hash,
    F: FnMut(G::EdgeRef) -> K,
    K: Measure + Copy,
   ```

## About the algorithm and implementation
The time complexity of bi-directional dijkstra is the same as normal dijkstra. However, in certain scenarios (e.g. grids and sparse road networks), it has to explore significantly less nodes to find the shortest path. https://www.ucl.ac.uk/~ucahmto/math/2020/05/30/bidirectional-dijkstra.html is a great resource on the correctness of the algorithm.

## Benchmarks
Under the right circumstances (large & sparse networks), it clearly shows that bidirectional dijkstra is faster than normal dijkstra.
```
test dijkstra_bench_grid ... bench: 469,582.30 ns/iter (+/- 12,469.78)
test dijkstra_bench_grid_bidirectional ... bench: 47,145.54 ns/iter (+/-
1,139.01)
test dijkstra_bench_grid_with_target ... bench: 118,156.60 ns/iter (+/-
3,168.78)
```

However, the existing benchmark also shows that it's not always beneficial.
```
test dijkstra_bench_random ... bench: 745,014.06 ns/iter (+/- 22,892.76)
test dijkstra_bench_random_bidirectional ... bench: 1,556,466.68 ns/iter
(+/- 77,702.84)
test dijkstra_bench_random_with_target ... bench: 694,060.94 ns/iter
(+/- 18,275.15)
```

On macbook pro M1

---------

Co-authored-by: Raoul Luqué <125205120+RaoulLuque@users.noreply.github.com>

Add [bidirectional
Dijkstra's](https://en.wikipedia.org/wiki/Bidirectional_search)
algorithm for the shortest path between two points.
```rust
pub fn bidirectional_dijkstra<G, F, K>(
    graph: G,
    start: G::NodeId,
    goal: G::NodeId,
    mut edge_cost: F,
) -> Option<K>
where
    G: Visitable + IntoEdgesDirected,
    G::NodeId: Eq + Hash,
    F: FnMut(G::EdgeRef) -> K,
    K: Measure + Copy,
   ```

The time complexity of bi-directional dijkstra is the same as normal dijkstra. However, in certain scenarios (e.g. grids and sparse road networks), it has to explore significantly less nodes to find the shortest path. https://www.ucl.ac.uk/~ucahmto/math/2020/05/30/bidirectional-dijkstra.html is a great resource on the correctness of the algorithm.

Under the right circumstances (large & sparse networks), it clearly shows that bidirectional dijkstra is faster than normal dijkstra.
```
test dijkstra_bench_grid ... bench: 469,582.30 ns/iter (+/- 12,469.78)
test dijkstra_bench_grid_bidirectional ... bench: 47,145.54 ns/iter (+/-
1,139.01)
test dijkstra_bench_grid_with_target ... bench: 118,156.60 ns/iter (+/-
3,168.78)
```

However, the existing benchmark also shows that it's not always beneficial.
```
test dijkstra_bench_random ... bench: 745,014.06 ns/iter (+/- 22,892.76)
test dijkstra_bench_random_bidirectional ... bench: 1,556,466.68 ns/iter
(+/- 77,702.84)
test dijkstra_bench_random_with_target ... bench: 694,060.94 ns/iter
(+/- 18,275.15)
```

On macbook pro M1

---------

Co-authored-by: Raoul Luqué <125205120+RaoulLuque@users.noreply.github.com>

## 🤖 New release

* `petgraph`: 0.8.2 -> 0.8.3 (✓ API compatible changes)

<details><summary><i><b>Changelog</b></i></summary><p>

<blockquote>

##
[0.8.3](https://github.com/petgraph/petgraph/compare/petgraph@v0.8.2...petgraph@v0.8.3)
- 2025-09-28

### Bug Fixes

- Infinite `subgraph_isomorphisms_iter` for empty isomorphisms
([#780](#780))
- Algos don't work on `UndirectedAdaptor`
([#870](#870))
([#871](#871))
- use a queue for SPFA
([#893](#893))
- `StableGraph::reverse` breaks free lists
([#890](#890))

### Documentation

- Fix examples link in README and unify typesetting of one word
([#823](#823))
- Add link to multigraph definition to isomorphism algos
([#824](#824))
- Fix auxiliary space (and time) complexity of bron-kerbosch
([#825](#825))
- Fix Typo in Operator Module Documentation
([#831](#831))
- Sync the crate feature flags in the README and docs
([#832](#832))
- Remove all \[Generic\] tags from algo docstrings
([#835](#835))
- Fix typos in comments
([#836](#836))
- Revamp CONTRIBUTING.md
([#833](#833))
- Update `GraphMap` link in README
([#857](#857))
- Add doc comment for `Dot::with_attr_getters`
([#850](#850))
- Specify iteration order for neighbors and edges and their variants
([#790](#790))
- Collection of Doc fixes
([#856](#856))

### New Features

- Add `into_nodes_edges_iters` to `StableGraph`
([#841](#841))
- Add methods to reserve & shrink `StableGraph` capacity
([#846](#846))
- Add Dinic's Maximum Flow Algorithm
([#739](#739))
- make Csr::from_sorted_edges generic over edge type and properly
increase edge_count in Csr::from_sorted_edges
([#861](#861))
- Add `map_owned` and `filter_map_owned` for `Graph` and `StableGraph`
([#863](#863))
- Add dijkstra::with_dynamic_goal
([#855](#855))
- Fix self-loop bug in all_simple_paths and enable multiple targets
([#865](#865))
- mark petgraph::dot::Dot::graph_fmt as public
([#866](#866))
- Add bidirectional Dijkstra algorithm
([#782](#782))

### Performance

- Make A* tie break on lower h-values
([#882](#882))

### Refactor

- add examples for scc algorithms and reorganize into dedicated module
([#830](#830))
- Remove unnecessary trait bounds from impls/methods
([#828](#828))
- replace uses of 'crate::util::zip' with 'core::iter::zip'
([#849](#849))
- Fix clippy (and other) lints
([#851](#851))
- Cleanup repo ([#854](#854))
- replace crate::util::enumerate with Iterator::enumerate
([#881](#881))

### Testing

- Add dependency list for 'quickcheck' feature
([#822](#822))
- Fix feature cfg capitalization in doctest
([#852](#852))
</blockquote>


</p></details>

---
This PR was generated with
[release-plz](https://github.com/release-plz/release-plz/).

---------

Co-authored-by: github-actions[bot] <41898282+github-actions[bot]@users.noreply.github.com>
Co-authored-by: Egor Starovoitov <52821033+starovoid@users.noreply.github.com>