Understanding Dijkstra’s Algorithm

January 25, 2025 | Algorithms

Dijkstra’s Algorithm is one of the most well-known algorithms in computer science, used to find the shortest path between nodes in a weighted graph. It’s widely applied in routing, mapping applications (like Google Maps), and network optimization.

Core Idea

Dijkstra’s algorithm starts at a source node and explores all reachable nodes while keeping track of the shortest known distance to each. It uses a greedy approach, always expanding the node with the smallest tentative distance.

How It Works

1. Assign every node a tentative distance:

   • 0 for the starting node.
   • ∞ for all other nodes.

2. Mark all nodes as unvisited. Set the starting node as the current node.

3. For the current node, consider all of its unvisited neighbors and calculate their tentative distances.

   • If the new distance is smaller, update it.

4. Once all neighbors are visited, mark the current node as visited.

5. Select the unvisited node with the smallest tentative distance as the new current node.

6. Repeat until all nodes are visited or the shortest path to the destination is found.

Example

Let’s find the shortest paths from node A.

Graph:
A → B (4)
A → C (2)
B → C (5)
B → D (10)
C → D (3)

Step-by-step

Shortest distances from A:

• To B: 4
• To C: 2
• To D: 5

Implementation

function dijkstra(graph, start) {
  const distances = {};
  const visited = new Set();

  // Initialize distances
  for (const node in graph) {
    distances[node] = node === start ? 0 : Infinity;
  }

  while (visited.size < Object.keys(graph).length) {
    // Select unvisited node with smallest distance
    const currentNode = Object.keys(distances)
      .filter(n => !visited.has(n))
      .reduce((a, b) => (distances[a] < distances[b] ? a : b));

    // Visit neighbors
    for (const [neighbor, weight] of Object.entries(graph[currentNode])) {
      const newDistance = distances[currentNode] + weight;
      if (newDistance < distances[neighbor]) {
        distances[neighbor] = newDistance;
      }
    }

    visited.add(currentNode);
  }

  return distances;
}

const graph = {
  A: { B: 4, C: 2 },
  B: { C: 5, D: 10 },
  C: { D: 3 },
  D: {}
};

console.log(dijkstra(graph, 'A'));

Expected Output

{ A: 0, B: 4, C: 2, D: 5 }

Time and Space Complexity

• Time Complexity: O(V^2) (basic version). Using a priority queue, it becomes O((V + E) log V).
• Space Complexity: O(V) for storing distances and visited nodes.