Dijkstra's Algorithm

If a graph has Unweighted Edges (every edge counts as a distance of 1), you can find the shortest path between two nodes using simple Breadth-First Search (BFS).

However, if the graph has Weighted Edges (e.g., Google Maps, where a highway is fast but a dirt road is slow), BFS will fail miserably. To find the absolute shortest path in a weighted graph, we use Dijkstra's Algorithm.

The Core Concept

Dijkstra's Algorithm is a Greedy Algorithm. It maintains an array of the minimum known distances from the Start Node to every other node (initially set to Infinity).

At each step, it:

1. Looks at all unvisited nodes.
2. Greedily picks the node with the absolute smallest known distance.
3. Examines that node's neighbors. If traveling through the current node offers a shorter path to the neighbor than previously known, it updates (relaxes) the neighbor's shortest distance.
4. Marks the current node as visited.

Why it Needs a Priority Queue (Min-Heap)

To execute Step 2 ("pick the unvisited node with the smallest distance"), you could scan the entire distance array. But scanning takes $O(V)$ time. Doing that $V$ times makes the algorithm $O(V^2)$. Instead, we throw the nodes and their current distances into a Min-Heap (Priority Queue). The Min-Heap allows us to instantly extract the closest unvisited node in $O(\log V)$ time!

If we just used BFS from A to B, we would take the direct edge (Weight: 4). But Dijkstra's knows that A -> C -> B is actually shorter (Weight: 1 + 2 = 3).

The Fatal Flaw: Negative Weights

Dijkstra's algorithm absolutely cannot handle negative edge weights. Because it is Greedy, once a node is marked as visited, its shortest path is considered completely final. If there is a hidden negative-weight edge further down the graph that acts as a "wormhole" to reduce the total cost, Dijkstra's will never see it. (If you have negative weights, you must use Bellman-Ford).

Implementation (TypeScript)

Note: JavaScript/TypeScript does not have a built-in Priority Queue. For this example, we will assume a generic MinPriorityQueue class exists that sorts by distance.

interface Edge {
  node: string;
  weight: number;
}

function dijkstra(graph: Map<string, Edge[]>, start: string): Map<string, number> {
  // Store the shortest known distance to every node
  const distances = new Map<string, number>();
  
  // Custom Priority Queue (Extracts node with minimum distance)
  const pq = new MinPriorityQueue(); 

  // Initialize all distances to Infinity
  for (const vertex of graph.keys()) {
    distances.set(vertex, Infinity);
  }
  
  // Distance to start node is 0
  distances.set(start, 0);
  pq.enqueue(start, 0);

  while (!pq.isEmpty()) {
    const { element: currentNode, priority: currentDist } = pq.dequeue();

    // Optimization: If we found a shorter path already, skip this stale queue entry
    if (currentDist > distances.get(currentNode)!) continue;

    // Explore neighbors
    const neighbors = graph.get(currentNode) || [];
    for (const edge of neighbors) {
      // Calculate new distance: Current Node's Dist + Edge Weight
      const newDist = currentDist + edge.weight;

      // If the new distance is SHORTER than the previously known distance
      if (newDist < distances.get(edge.node)!) {
        // Update the shortest distance map
        distances.set(edge.node, newDist);
        // Push the better path into the priority queue
        pq.enqueue(edge.node, newDist);
      }
    }
  }

  return distances;
}

Time & Space Complexity

Using an Adjacency List and a Min-Heap (Priority Queue):

• Time Complexity: $O((V + E) \log V)$. We process every edge, and priority queue operations take logarithmic time.
• Space Complexity: $O(V)$. For the distance hash map and the priority queue.