Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest paths from a source vertex to all other vertices in a weighted graph with non-negative edge weights. It's a greedy algorithm that uses a priority queue.

---

Why This Matters in Interviews

Dijkstra's algorithm is important because:

• Shortest path problems: Common in system design (routing, networking)
• Greedy algorithms: Demonstrates greedy approach
• Priority queue usage: Tests understanding of data structures
• Graph algorithms: Foundation for many graph problems

Interviewers use Dijkstra's to assess your understanding of graph algorithms, greedy strategies, and your ability to implement complex algorithms efficiently.

---

Core Concepts

• Greedy approach: Always chooses closest unvisited vertex
• Relaxation: Updating shortest distance if better path found
• Priority queue: Maintains vertices by distance
• Non-negative weights: Algorithm requires non-negative edges
• Single-source: Finds shortest paths from one source
• Optimal substructure: Shortest path contains shortest subpaths

---

Detailed Explanation

Algorithm Steps

1. Initialize distances: source = 0, all others = infinity
2. Create priority queue with all vertices
3. While queue not empty:
   a. Extract vertex u with minimum distance
   b. Mark u as visited
   c. For each neighbor v of u:
      - If distance[u] + weight(u,v) < distance[v]:
        - Update distance[v]
        - Update priority queue
4. Return distances

Implementation

Basic Implementation:

class Dijkstra {
  private graph: Map<number, Array<[number, number]>>; // [neighbor, weight]
  
  constructor(graph: Map<number, Array<[number, number]>>) {
    this.graph = graph;
  }
  
  shortestPath(source: number): Map<number, number> {
    const distances = new Map<number, number>();
    const visited = new Set<number>();
    const pq = new MinPriorityQueue<[number, number]>(); // [distance, vertex]
    
    // Initialize distances
    for (const vertex of this.graph.keys()) {
      distances.set(vertex, Infinity);
    }
    distances.set(source, 0);
    pq.insert([0, source]);
    
    while (!pq.isEmpty()) {
      const [dist, u] = pq.extractMin()!;
      
      if (visited.has(u)) continue;
      visited.add(u);
      
      // Relax neighbors
      for (const [v, weight] of this.graph.get(u) || []) {
        if (visited.has(v)) continue;
        
        const newDist = dist + weight;
        if (newDist < distances.get(v)!) {
          distances.set(v, newDist);
          pq.insert([newDist, v]);
        }
      }
    }
    
    return distances;
  }
}

// Time: O((V + E) log V) with binary heap
// Space: O(V)

With Path Reconstruction:

class DijkstraWithPath {
  shortestPath(
    graph: Map<number, Array<[number, number]>>, 
    source: number, 
    target: number
  ): { distance: number; path: number[] } | null {
    const distances = new Map<number, number>();
    const previous = new Map<number, number | null>();
    const pq = new MinPriorityQueue<[number, number]>();
    
    // Initialize
    for (const vertex of graph.keys()) {
      distances.set(vertex, Infinity);
      previous.set(vertex, null);
    }
    distances.set(source, 0);
    pq.insert([0, source]);
    
    while (!pq.isEmpty()) {
      const [dist, u] = pq.extractMin()!;
      
      if (u === target) {
        // Reconstruct path
        const path: number[] = [];
        let current: number | null = target;
        while (current !== null) {
          path.unshift(current);
          current = previous.get(current)!;
        }
        return { distance: dist, path };
      }
      
      for (const [v, weight] of graph.get(u) || []) {
        const newDist = dist + weight;
        if (newDist < distances.get(v)!) {
          distances.set(v, newDist);
          previous.set(v, u);
          pq.insert([newDist, v]);
        }
      }
    }
    
    return null; // No path
  }
}

Priority Queue Implementation

class MinPriorityQueue<T extends [number, any]> {
  private heap: T[] = [];
  
  insert(item: T): void {
    this.heap.push(item);
    this.bubbleUp(this.heap.length - 1);
  }
  
  extractMin(): T | null {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop()!;
    
    const min = this.heap[0];
    this.heap[0] = this.heap.pop()!;
    this.bubbleDown(0);
    return min;
  }
  
  isEmpty(): boolean {
    return this.heap.length === 0;
  }
  
  private bubbleUp(index: number): void {
    while (index > 0) {
      const parent = Math.floor((index - 1) / 2);
      if (this.heap[parent][0] <= this.heap[index][0]) break;
      [this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]];
      index = parent;
    }
  }
  
  private bubbleDown(index: number): void {
    while (true) {
      let smallest = index;
      const left = 2 * index + 1;
      const right = 2 * index + 2;
      
      if (left < this.heap.length && this.heap[left][0] < this.heap[smallest][0]) {
        smallest = left;
      }
      if (right < this.heap.length && this.heap[right][0] < this.heap[smallest][0]) {
        smallest = right;
      }
      
      if (smallest === index) break;
      [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
      index = smallest;
    }
  }
}

---

Examples

Network Routing

class NetworkRouter {
  private network: Map<string, Array<[string, number]>>;
  
  findShortestPath(source: string, destination: string): string[] | null {
    const distances = new Map<string, number>();
    const previous = new Map<string, string | null>();
    const pq = new MinPriorityQueue<[number, string]>();
    
    distances.set(source, 0);
    pq.insert([0, source]);
    
    while (!pq.isEmpty()) {
      const [dist, node] = pq.extractMin()!;
      
      if (node === destination) {
        return this.reconstructPath(previous, source, destination);
      }
      
      for (const [neighbor, latency] of this.network.get(node) || []) {
        const newDist = dist + latency;
        if (!distances.has(neighbor) || newDist < distances.get(neighbor)!) {
          distances.set(neighbor, newDist);
          previous.set(neighbor, node);
          pq.insert([newDist, neighbor]);
        }
      }
    }
    
    return null;
  }
  
  private reconstructPath(
    previous: Map<string, string | null>,
    source: string,
    destination: string
  ): string[] {
    const path: string[] = [];
    let current: string | null = destination;
    
    while (current !== null) {
      path.unshift(current);
      current = previous.get(current)!;
    }
    
    return path;
  }
}

All Shortest Paths

function allShortestPaths(
  graph: Map<number, Array<[number, number]>>,
  source: number
): Map<number, { distance: number; path: number[] }> {
  const distances = new Map<number, number>();
  const previous = new Map<number, number | null>();
  const pq = new MinPriorityQueue<[number, number]>();
  const results = new Map<number, { distance: number; path: number[] }>();
  
  distances.set(source, 0);
  pq.insert([0, source]);
  
  while (!pq.isEmpty()) {
    const [dist, u] = pq.extractMin()!;
    
    // Store result for this vertex
    const path = reconstructPath(previous, source, u);
    results.set(u, { distance: dist, path });
    
    for (const [v, weight] of graph.get(u) || []) {
      const newDist = dist + weight;
      if (!distances.has(v) || newDist < distances.get(v)!) {
        distances.set(v, newDist);
        previous.set(v, u);
        pq.insert([newDist, v]);
      }
    }
  }
  
  return results;
}

---

Common Pitfalls

• Negative weights: Algorithm fails with negative edges. Fix: Use Bellman-Ford for negative weights
• Not using priority queue: O(V²) instead of O((V+E)log V). Fix: Always use priority queue
• Not checking visited: Processing same vertex multiple times. Fix: Mark visited or skip if already processed
• Integer overflow: Large distances overflow. Fix: Use appropriate data types, check bounds
• Not reconstructing path: Only getting distances. Fix: Store previous vertices

---

Interview Questions

Beginner

Q: What is Dijkstra's algorithm and what are its requirements?

A:

Dijkstra's Algorithm finds shortest paths from a source vertex to all other vertices in a weighted graph.

Requirements:

• Non-negative edge weights: Algorithm fails with negative weights
• Weighted graph: Edges have weights (distances, costs)
• Connected graph: All vertices reachable (or handle disconnected)

How it works:

1. Start with source distance = 0, all others = infinity
2. Use priority queue to always process closest unvisited vertex
3. Relax (update) distances to neighbors
4. Repeat until all vertices processed

Time Complexity:

• With binary heap: O((V + E) log V)
• With Fibonacci heap: O(E + V log V)

Space Complexity: O(V)

Example:

Graph: A--5--B
        \   /
         3 2
          \/
          C

Source: A
Distances: A=0, B=5, C=3
Shortest path A→C: A→C (3)

---

Intermediate

Q: Implement Dijkstra's algorithm with path reconstruction. How do you optimize it?

A:

class OptimizedDijkstra {
  shortestPath(
    graph: Map<number, Array<[number, number]>>,
    source: number,
    target: number
  ): { distance: number; path: number[] } | null {
    const distances = new Map<number, number>();
    const previous = new Map<number, number | null>();
    const pq = new MinPriorityQueue<[number, number]>();
    const visited = new Set<number>();
    
    // Initialize
    for (const vertex of graph.keys()) {
      distances.set(vertex, Infinity);
    }
    distances.set(source, 0);
    pq.insert([0, source]);
    
    while (!pq.isEmpty()) {
      const [dist, u] = pq.extractMin()!;
      
      // Early termination
      if (u === target) {
        return {
          distance: dist,
          path: this.reconstructPath(previous, source, target)
        };
      }
      
      if (visited.has(u)) continue;
      visited.add(u);
      
      // Relax neighbors
      for (const [v, weight] of graph.get(u) || []) {
        if (visited.has(v)) continue;
        
        const newDist = dist + weight;
        const oldDist = distances.get(v) ?? Infinity;
        
        if (newDist < oldDist) {
          distances.set(v, newDist);
          previous.set(v, u);
          pq.insert([newDist, v]);
        }
      }
    }
    
    return null;
  }
  
  private reconstructPath(
    previous: Map<number, number | null>,
    source: number,
    target: number
  ): number[] {
    const path: number[] = [];
    let current: number | null = target;
    
    while (current !== null) {
      path.unshift(current);
      current = previous.get(current)!;
      if (current === source) {
        path.unshift(source);
        break;
      }
    }
    
    return path;
  }
}

// Optimizations:
// 1. Early termination when target found
// 2. Skip already visited vertices
// 3. Use efficient priority queue (binary heap)
// 4. Bidirectional search for point-to-point queries

---

Senior

Q: Design a routing system for a distributed network using Dijkstra's algorithm. Handle dynamic edge weights, node failures, and optimize for millions of nodes.

A:

class DistributedRouting {
  private graph: DistributedGraph;
  private cache: Cache;
  private updateQueue: UpdateQueue;
  
  constructor(graph: DistributedGraph, cache: Cache) {
    this.graph = graph;
    this.cache = cache;
    this.updateQueue = new UpdateQueue();
  }
  
  async findShortestPath(
    source: string,
    target: string,
    constraints?: RouteConstraints
  ): Promise<Route | null> {
    // Check cache
    const cacheKey = this.getCacheKey(source, target, constraints);
    const cached = await this.cache.get(cacheKey);
    if (cached && !this.isStale(cached)) {
      return cached;
    }
    
    // Use A* with heuristic for better performance
    const route = await this.aStarSearch(source, target, constraints);
    
    if (route) {
      await this.cache.set(cacheKey, route, 300); // Cache 5 minutes
    }
    
    return route;
  }
  
  private async aStarSearch(
    source: string,
    target: string,
    constraints?: RouteConstraints
  ): Promise<Route | null> {
    const gScore = new Map<string, number>(); // Actual distance
    const fScore = new Map<string, number>(); // g + heuristic
    const previous = new Map<string, string | null>();
    const openSet = new MinPriorityQueue<[number, string]>();
    const closedSet = new Set<string>();
    
    gScore.set(source, 0);
    fScore.set(source, this.heuristic(source, target));
    openSet.insert([fScore.get(source)!, source]);
    
    while (!openSet.isEmpty()) {
      const [_, current] = openSet.extractMin()!;
      
      if (current === target) {
        return this.buildRoute(previous, source, target);
      }
      
      closedSet.add(current);
      
      // Get neighbors from distributed graph
      const neighbors = await this.graph.getNeighbors(current);
      
      for (const neighbor of neighbors) {
        if (closedSet.has(neighbor)) continue;
        
        // Get edge weight (may be dynamic)
        const weight = await this.getEdgeWeight(current, neighbor, constraints);
        if (weight === null) continue; // Edge doesn't meet constraints
        
        const tentativeG = (gScore.get(current) ?? Infinity) + weight;
        const currentG = gScore.get(neighbor) ?? Infinity;
        
        if (tentativeG < currentG) {
          previous.set(neighbor, current);
          gScore.set(neighbor, tentativeG);
          fScore.set(neighbor, tentativeG + this.heuristic(neighbor, target));
          
          if (!openSet.contains(neighbor)) {
            openSet.insert([fScore.get(neighbor)!, neighbor]);
          } else {
            openSet.update(neighbor, fScore.get(neighbor)!);
          }
        }
      }
    }
    
    return null;
  }
  
  private heuristic(node: string, target: string): number {
    // Use geographic distance or network latency estimate
    // Must be admissible (never overestimate)
    return this.estimateDistance(node, target);
  }
  
  private async getEdgeWeight(
    from: string,
    to: string,
    constraints?: RouteConstraints
  ): Promise<number | null> {
    // Check for node failures
    if (await this.isNodeDown(to)) {
      return null;
    }
    
    // Get current weight (may be updated)
    const weight = await this.graph.getEdgeWeight(from, to);
    
    // Apply constraints
    if (constraints) {
      if (constraints.maxLatency && weight > constraints.maxLatency) {
        return null;
      }
      if (constraints.avoidNodes && constraints.avoidNodes.includes(to)) {
        return null;
      }
    }
    
    return weight;
  }
  
  // Handle dynamic updates
  async updateEdgeWeight(from: string, to: string, newWeight: number): Promise<void> {
    await this.graph.updateEdgeWeight(from, to, newWeight);
    
    // Invalidate affected cached routes
    await this.invalidateAffectedRoutes(from, to);
    
    // Queue for batch processing
    this.updateQueue.add({ from, to, weight: newWeight });
  }
  
  private async invalidateAffectedRoutes(from: string, to: string): Promise<void> {
    // Invalidate routes that might use this edge
    const patterns = [`*:${from}:*`, `*:*:${to}`, `*:${from}:${to}`];
    for (const pattern of patterns) {
      await this.cache.deletePattern(pattern);
    }
  }
  
  private buildRoute(
    previous: Map<string, string | null>,
    source: string,
    target: string
  ): Route {
    const path: string[] = [];
    let current: string | null = target;
    const totalDistance = 0; // Calculate from gScore
    
    while (current !== null) {
      path.unshift(current);
      current = previous.get(current)!;
      if (current === source) {
        path.unshift(source);
        break;
      }
    }
    
    return {
      path,
      distance: totalDistance,
      hops: path.length - 1
    };
  }
  
  private estimateDistance(node: string, target: string): number {
    // Use geographic coordinates or network topology
    return 0; // Placeholder
  }
  
  private async isNodeDown(node: string): Promise<boolean> {
    // Check node health status
    return false;
  }
  
  private getCacheKey(source: string, target: string, constraints?: RouteConstraints): string {
    return `route:${source}:${target}:${JSON.stringify(constraints)}`;
  }
  
  private isStale(cached: Route): boolean {
    // Check if cached route is still valid
    return false;
  }
}

interface Route {
  path: string[];
  distance: number;
  hops: number;
}

interface RouteConstraints {
  maxLatency?: number;
  avoidNodes?: string[];
  requiredNodes?: string[];
}

Features:

1. A algorithm*: Uses heuristic for faster search
2. Caching: Cache routes to avoid recomputation
3. Dynamic updates: Handle changing edge weights
4. Failure handling: Skip failed nodes
5. Constraints: Support routing constraints
6. Distributed: Works with distributed graph storage

---

Key Takeaways

• Dijkstra's algorithm: Finds shortest paths in weighted graphs
• Requirements: Non-negative edge weights, weighted graph
• Greedy approach: Always processes closest unvisited vertex
• Priority queue: Essential for O((V+E)log V) performance
• Time complexity: O((V+E)log V) with binary heap
• Path reconstruction: Store previous vertices to build path
• Limitations: Doesn't work with negative weights (use Bellman-Ford)