Implement bidirectional Dijkstra for shortest paths

Q: Implement bidirectional Dijkstra for shortest paths

This is a Coding & Algorithms interview question from Citi for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Given a directed or undirected graph with non‑negative edge weights, design and implement bidirectional Dijkstra (“double Dijkstra”) to find the shortest path between a single source s and target t. Specify the data structures for the forward and reverse searches, the termination condition, how to compute the correct shortest distance when the frontiers meet, and how to reconstruct the full path. Analyze time and space complexity versus standard Dijkstra, and discuss edge cases such as disconnected graphs and multiple shortest paths.

Implement bidirectional Dijkstra for shortest paths

Comments (0)