Dijkstra's Algorithm

Dijkstra's Algorithm

Ever wondered how Google Maps finds the fastest route between two cities? That's Dijkstra's algorithm in action! It finds the shortest path from a source vertex to all other vertices in a weighted graph.

The genius of Dijkstra's is its greedy approach — at each step, it picks the vertex with the smallest known distance from the source. It's like always choosing the closest unvisited city on a road trip.

How It Works

Start by setting the distance to the source vertex as 0 and all others as infinity. Then, repeatedly select the unvisited vertex with the smallest distance, and update the distances of its neighbors.

The key insight is that once a vertex is visited, its shortest distance is final. Why? Because any other path to it would have to go through a vertex that's farther away first, which contradicts the greedy choice.

function dijkstra(graph, start) {
  const distances = {};
  const visited = new Set();
  
  for (const vertex in graph) {
    distances[vertex] = Infinity;
  }
  distances[start] = 0;
  
  while (visited.size < Object.keys(graph).length) {
    let current = null;
    for (const vertex in distances) {
      if (!visited.has(vertex) && 
          (current === null || distances[vertex] < distances[current])) {
        current = vertex;
      }
    }
    
    if (distances[current] === Infinity) break;
    visited.add(current);
    
    for (const neighbor of graph[current]) {
      const distance = distances[current] + neighbor.weight;
      if (distance < distances[neighbor.vertex]) {
        distances[neighbor.vertex] = distance;
      }
    }
  }
  return distances;
}

Step-by-Step Example

Let's say we have cities connected by roads with different distances. Starting from City A, Dijkstra's will first mark A as visited (distance 0), then check all neighbors and update their distances.

Next, it picks the closest unvisited city (say B at distance 5), marks it visited, and updates its neighbors. This continues until all reachable cities are visited. The result is the shortest distance from A to every other city!

const cities = {
  A: [{ vertex: "B", weight: 4 }, { vertex: "C", weight: 2 }],
  B: [{ vertex: "C", weight: 1 }, { vertex: "D", weight: 5 }],
  C: [{ vertex: "B", weight: 1 }, { vertex: "D", weight: 8 }],
  D: []
};

Limitations

Dijkstra's has one big limitation — it doesn't work with negative weights. Why? Because once a vertex is marked as visited, we assume its distance is final. But a negative edge could provide a shorter path later, breaking this assumption.

If your graph has negative weights, you'll need the Bellman-Ford algorithm instead. But for most real-world applications like navigation and network routing, Dijkstra's is the way to go!