---
title: "Find a shortest path with bidirectional Dijkstra in C#"
url: https://recursiveai.org/onepath/cookbook/route-graph-with-bidirectional-search/
description: "Find the shortest path on a directed, weighted graph with bidirectional Dijkstra in C# and compare its cost with ordinary Dijkstra."
version: "1.2.0"
---

# Find a shortest path with bidirectional Dijkstra in C#

**OnePath** is a free, open-source pathfinding library for .NET from Recursive AI. MIT or Apache-2.0, no native dependencies.

[NuGet](https://www.nuget.org/packages/RecursiveAI.OnePath) · [GitHub](https://github.com/recursive-ai-oss/onepath-csharp) · [Docs](https://recursiveai.org/onepath/docs/) · [Download example (.zip)](https://recursiveai.org/onepath/cookbook/route-graph-with-bidirectional-search/route-graph-with-bidirectional-search.zip)

Bidirectional Dijkstra finds a shortest path by searching from both ends of a weighted graph.

```shell
dotnet add package RecursiveAI.OnePath
```

Requires [.NET 10](https://dotnet.microsoft.com/download/dotnet/10.0) (net10.0); .NET 9 and earlier aren’t supported.

```csharp
using RecursiveAI.OnePath;

GraphEdge[] edges =
[
    new(0, 1, 1), new(1, 3, 9),
    new(0, 2, 4), new(2, 3, 2)
];
var graph = Graph.From(edges, directed: true);
var options = new GraphOptions
{
    Algorithm =
        GraphAlgorithm.BidirectionalDijkstra
};
var path = graph.FindPath(0, 3, options);
if (!path.Found)
    throw new InvalidOperationException(
        path.Status.ToString());
var nodes = path.Nodes.ToArray();
Console.WriteLine(string.Join(" -> ", nodes));
Console.WriteLine($"Cost: {path.Cost}");
```

The cheapest route costs 6, even though both possible routes take two edges.

Unzip [the example](https://recursiveai.org/onepath/cookbook/route-graph-with-bidirectional-search/route-graph-with-bidirectional-search.zip), then `dotnet run`.

```text
0 -> 2 -> 3
Cost: 6
```

## The full program

The program uses the four directed edges shown above and runs ordinary Dijkstra on the same graph as a reference. It prints the algorithm used and compares total costs.

```csharp
using RecursiveAI.OnePath;

GraphEdge[] edges =
[
    new(0, 1, 1), new(1, 3, 9),
    new(0, 2, 4), new(2, 3, 2)
];
var graph = Graph.From(edges, directed: true);
var options = new GraphOptions
{
    Algorithm =
        GraphAlgorithm.BidirectionalDijkstra
};
var path = graph.FindPath(0, 3, options);
if (!path.Found)
    throw new InvalidOperationException(
        path.Status.ToString());
var nodes = path.Nodes.ToArray();
Console.WriteLine(string.Join(" -> ", nodes));
Console.WriteLine($"Cost: {path.Cost}");

Console.WriteLine($"Algorithm: {path.Algorithm}");
var reference = graph.FindPath(0, 3, new GraphOptions
{
    Algorithm = GraphAlgorithm.Dijkstra
});
Console.WriteLine($"Dijkstra cost: {reference.Cost}");
Console.WriteLine($"Same shortest cost: {reference.Found && reference.Cost == path.Cost}");
```

`dotnet run` prints:

```text
0 -> 2 -> 3
Cost: 6
Algorithm: BidirectionalDijkstra
Dijkstra cost: 6
Same shortest cost: True
```

If there is no route, `Found` is `false` and `Status` is `NoPath`; check the status before consuming the node sequence.

## Variations

To see that a backward search doesn’t make the graph undirected, append this snippet to the full program. The reverse trip has no route.

```csharp
var reverse = graph.FindPath(3, 0, options);
Console.WriteLine($"Reverse: {reverse.Status}");
```

```text
Reverse: NoPath
```

## Related recipes

- [Find routes on a weighted graph](https://recursiveai.org/onepath/cookbook/graph-routes/)
- [Use landmarks for graph searches](https://recursiveai.org/onepath/cookbook/speed-graph-search-with-landmarks/)

## The short answer

Build your weighted graph with `Graph.From`, pass `directed: true` for one-way edges, and set `GraphOptions.Algorithm` to `BidirectionalDijkstra`. The graph stores reverse adjacency for the backward search; you supply only edges that actually exist. On success, `Nodes` lists the path from start to goal and `Cost` is the total edge weight. Here `0 → 2 → 3` costs `4 + 2 = 6`, beating `0 → 1 → 3` at `1 + 9 = 10`.

## What is the bidirectional Dijkstra algorithm?

Ordinary Dijkstra searches out from the start by increasing known cost. The bidirectional variant keeps two such queues: one per direction, alternating forward and backward expansions in OnePath. A node reached by both searches supplies a candidate total cost: the cost from the start to the node plus the cost from the node to the goal. When the search finishes, it joins the two parent chains into a route.

Use `BidirectionalDijkstra` when you want a weighted search without a heuristic or precomputed landmark distances. Unlike landmark search, it does not need a table of distances to selected nodes. The graph itself still stores outgoing and incoming edge lists. Weights must be finite and nonnegative; zero is allowed. Compare total costs rather than the exact node lists when checking against ordinary Dijkstra: there may be more than one route with the same minimum cost. The sample uses small integer weights so its sums compare exactly; fractional weights can differ by floating-point rounding.

## How does bidirectional Dijkstra work on a directed graph?

The forward search follows outgoing edges. The search from the goal follows **incoming** edges, retaining each edge’s original weight and direction for the reconstructed route. For example, from node 3 the backward search may inspect `2 → 3`, but that inspection does not add `3 → 2` as an edge. Adding reverse edges yourself would change which trips are possible. So would omitting `directed: true` in `Graph.From`, whose default adds both directions for every edge listed.

## Can bidirectional Dijkstra stop at the first meeting?

No. After exploring from node 0, the search has costs 1 and 4 to nodes 1 and 2 respectively. From node 3, the incoming edge from node 1 supplies a route costing 10. The incoming edge from node 2 supplies a cheaper route costing 6. Stopping at the first candidate could miss the minimum. For this zero-heuristic search, OnePath continues until the cheapest pending costs on the two sides sum to at least the best route cost, or one side runs out of nodes to visit. The [graph reference](https://recursiveai.org/onepath/docs/graphs/#bidirectional-search) describes the meeting and stopping rules.
