CS Algorithms 101 – Dijkstra’s Algorithm

Dijkstra’s algorithm is a shortest-path algorithm that finds the shortest path between a source vertex and all other vertices in a weighted graph.

The algorithm works by assigning a tentative distance value to every vertex in the graph, and then iteratively selecting the vertex with the smallest tentative distance and updating the tentative distances of its neighboring vertices.

Here’s an example of implementing Dijkstra’s algorithm in JavaScript:

function dijkstra(graph, source) {
  const distances = {};
  const visited = {};
  const pq = new PriorityQueue();

  // Initialize distances to all vertices as Infinity
  for (const vertex in graph) {
    distances[vertex] = Infinity;
  }

  // Set the distance to the source vertex as 0
  distances[source] = 0;

  // Add the source vertex to the priority queue
  pq.enqueue(source, 0);

  while (!pq.isEmpty()) {
    const { vertex: current } = pq.dequeue();

    if (visited[current]) {
      continue;
    }

    visited[current] = true;

    for (const neighbor in graph[current]) {
      const distance = graph[current][neighbor];
      const tentativeDistance = distances[current] + distance;

      if (tentativeDistance < distances[neighbor]) {
        distances[neighbor] = tentativeDistance;
        pq.enqueue(neighbor, tentativeDistance);
      }
    }
  }

  return distances;
}

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

const distances = dijkstra(graph, 'A');
console.log(distances); // Output: { A: 0, B: 5, C: 2, D: 6 }

In this example, the dijkstra function takes a graph object and a source vertex as input, and returns an object containing the shortest distances from the source vertex to all other vertices in the graph. The function works by initializing all distances to infinity except the distance to the source vertex, which is set to 0. It then uses a priority queue to select the vertex with the smallest tentative distance and update the tentative distances of its neighboring vertices.

The PriorityQueue class is not shown here, but it can be implemented using a binary heap or another data structure that supports efficient insertion and removal of elements with priority.