Bidirectional Dijkstra
Dijkstra from both source and target simultaneously, meeting in middle for faster pathfinding.
Visualization
Interactive visualization for Bidirectional Dijkstra
Bidirectional Dijkstra:
- • Search from both source & target
- • Faster for large graphs
Interactive visualization with step-by-step execution
Implementation
1function bidirectionalDijkstra(graph: Map<number, [number, number][]>, revGraph: Map<number, [number, number][]>, source: number, target: number): number {
2 const distF = new Map<number, number>([[source, 0]]);
3 const distB = new Map<number, number>([[target, 0]]);
4 const pqF: [number, number][] = [[0, source]];
5 const pqB: [number, number][] = [[0, target]];
6
7 let best = Infinity;
8
9 while (pqF.length || pqB.length) {
10 if (pqF.length) {
11 pqF.sort((a, b) => a[0] - b[0]);
12 const [dF, uF] = pqF.shift()!;
13 if (dF > (distF.get(uF) ?? Infinity)) continue;
14 if (distB.has(uF)) best = Math.min(best, dF + distB.get(uF)!);
15 if (dF >= best) break;
16
17 for (const [v, w] of graph.get(uF) ?? []) {
18 const alt = dF + w;
19 if (alt < (distF.get(v) ?? Infinity)) {
20 distF.set(v, alt);
21 pqF.push([alt, v]);
22 }
23 }
24 }
25
26 if (pqB.length) {
27 pqB.sort((a, b) => a[0] - b[0]);
28 const [dB, uB] = pqB.shift()!;
29 if (dB > (distB.get(uB) ?? Infinity)) continue;
30 if (distF.has(uB)) best = Math.min(best, dB + distF.get(uB)!);
31 if (dB >= best) break;
32
33 for (const [v, w] of revGraph.get(uB) ?? []) {
34 const alt = dB + w;
35 if (alt < (distB.get(v) ?? Infinity)) {
36 distB.set(v, alt);
37 pqB.push([alt, v]);
38 }
39 }
40 }
41 }
42 return best === Infinity ? -1 : best;
43}Deep Dive
Theoretical Foundation
Run Dijkstra from source and target simultaneously. Stop when search frontiers meet. Explores ~2×(d/2) nodes vs d nodes, significant speedup.
Complexity
Time
O((V+E) log V)
O((V+E) log V)
O((V+E) log V)
Space
O(V)
Applications
Industry Use
Turn-by-turn GPS routing
Social network distance queries
Game AI pathfinding on large maps
Logistics and delivery route planning
Telecommunications routing
Multi-criteria path exploration
Use Cases
Related Algorithms
Depth-First Search (DFS)
Graph traversal exploring as deep as possible before backtracking. DFS is a fundamental algorithm that uses a stack (either implicitly through recursion or explicitly) to explore graph vertices. It's essential for cycle detection, topological sorting, and pathfinding problems.
Breadth-First Search (BFS)
Level-by-level graph traversal guaranteeing shortest paths in unweighted graphs. BFS uses a queue to explore vertices level by level, making it optimal for finding shortest paths and solving problems that require exploring nearest neighbors first.
Dijkstra's Algorithm
Finds shortest path from source to all vertices in weighted graph with non-negative edges. Uses greedy approach with priority queue.
Floyd-Warshall Algorithm
Floyd-Warshall is an all-pairs shortest path algorithm that finds shortest distances between every pair of vertices in a weighted graph. Unlike Dijkstra (single-source), it computes shortest paths from all vertices to all other vertices simultaneously. The algorithm can handle negative edge weights but not negative cycles. Developed independently by Robert Floyd, Bernard Roy, and Stephen Warshall in the early 1960s.