Explain and implement Dijkstra's algorithm for shortest paths
Reported in Improbable European engineering loops. Graph algorithm for non-negative edge weights using priority queue.
Interview scenario
Context for Improbable candidates:
Given weighted directed graph and source node, return shortest distances to all nodes.
Model answer
Try answering aloud first
Cover trade-offs, structure, and a concrete example before revealing the baseline response.
How to frame this at Improbable: Connect your answer to measurable impact, clarity of thought, and trade-offs the team cares about. Below is a strong baseline response you can adapt with your own project examples.
Dijkstra greedily settles the closest unvisited node using a min-heap. Maintain dist[v] initialized to ∞ except source 0. Pop smallest tentative distance; relax all edges to neighbors if shorter path found.
Complexity: O((V + E) log V) with binary heap. Requires non-negative weights—negative edges need Bellman-Ford.
Implementation details: use adjacency list; lazy decrease-key via pushing duplicate entries and ignoring stale pops; track predecessors for path reconstruction.
Contrast with BFS (unweighted), A* (heuristic-guided), and Floyd-Warshall (all pairs). Real-world uses: routing, map ETA, network latency in service meshes.
Discussion
Comments (0)
Share how this question came up in your loop, or add tips for others preparing.
Log in to comment on this question.