Bidirectional Dijkstra finds a shortest path by searching from both ends of a weighted graph.
dotnet add package RecursiveAI.OnePathRequires .NET 10 (net10.0); .NET 9 and earlier aren’t supported.
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, then dotnet run.
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.
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:
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.
var reverse = graph.FindPath(3, 0, options); Console.WriteLine($"Reverse: {reverse.Status}");
Reverse: NoPathRelated recipes
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 describes the meeting and stopping rules.