Skip to main content

Dijkstra's Algorithm

Dijkstra's Algorithm​

Dijkstra's Algorithm is a classic algorithm used for finding the shortest path between nodes in a graph. It works well with graphs where all edge weights are non-negative. The algorithm efficiently finds the shortest path from a source node to all other nodes in the graph.

Algorithm Overview​

  1. Initialization:

    • Set the distance to the source node to 0 and all other nodes to infinity.
    • Use a priority queue (min-heap) to store nodes with their distances.

  2. Process Nodes:

    • Extract the node with the minimum distance from the priority queue.
    • Update the distances to its neighboring nodes.
    • If a shorter path is found, update the distance and add the neighbor to the priority queue.

  3. Termination:

    • The algorithm terminates when all nodes have been processed, or the priority queue is empty.

Steps of the Algorithm​

  1. Initialize Distances:
function dijkstra(graph, start) {
  const distances = {};
  const prev = {};
  const pq = new MinHeap();

  // Initialize distances and priority queue
  for (const node in graph) {
    distances[node] = Infinity;
    prev[node] = null;
  }
  distances[start] = 0;
  pq.enqueue(start, 0);

  while (pq.heap.length > 0) {
    const { node: u } = pq.dequeue();

    for (const neighbor in graph[u]) {
      const alt = distances[u] + graph[u][neighbor];
      if (alt < distances[neighbor]) {
        distances[neighbor] = alt;
        prev[neighbor] = u;
        pq.enqueue(neighbor, alt);
      }
    }
  }

  return { distances, prev };
}

// Example usage:
const graph = {
  A: { B: 1, C: 4 },
  B: { C: 2, D: 5 },
  C: { D: 1 },
  D: {}
};

const { distances, prev } = dijkstra(graph, 'A');

Some common Dijkstra's Problems

Graph Problems​

Pathfinding and Search Problems​

Network Delay​