Intermediate LevelData Structures & Algorithms
How does Dijkstra's Algorithm find the Shortest Path in a weighted graph?
ā Interview Prompt: Explain Dijkstra's greedy shortest-path algorithm, min-priority queue, O((V+E) log V) complexity, and its constraint (non-negative weights).
Dijkstra's Algorithm finds shortest paths from a source vertex to all other vertices in a graph with non-negative edge weights.
Steps:
1
Initialise distance array:
dist[source] = 0, all others = $\infty$.2
Use a min-priority queue (min-heap) ordered by distance.
3
While heap is non-empty:
ā¢
Extract vertex $u$ with minimum distance.
ā¢
For each neighbour $v$ with edge weight $w$:
ā¢
If
dist[u] + w < dist[v] ā relax the edge: update dist[v] and push $v$ to heap.4
Result:
dist[] = shortest distances from source.ā¢
Complexity: $O((V + E) \log V)$ with binary min-heap.
ā¢
Constraint: Fails with negative edge weights ā use Bellman-Ford instead.
Code Implementation Example
typescript
// Simplified Dijkstra using sorted array as min-heap simulation
function dijkstra(graph: Map<number, [number, number][]>, src: number, V: number): number[] {
const dist = new Array(V).fill(Infinity);
dist[src] = 0;
const visited = new Set<number>();
const pq: [number, number][] = [[0, src]]; // [dist, node]
while (pq.length) {
pq.sort((a, b) => a[0] - b[0]);
const [d, u] = pq.shift()!;
if (visited.has(u)) continue;
visited.add(u);
for (const [v, w] of graph.get(u) ?? []) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push([dist[v], v]);
}
}
}
return dist;
}š”Dijkstra's shortest-path with greedy edge relaxation.
šÆ Interview Key Takeaway
Dijkstra's O((V+E)log V) requires non-negative weights. For negative weights use Bellman-Ford O(VE). For all-pairs use Floyd-Warshall O(VĀ³).
#DSA#Dijkstra#Graph#Shortest Path#Intermediate
Back to all Data Structures & Algorithms Questionsā