DSA Dijkstra's

Shortestpath: Advanced Dijkstra's Algorithm

In our previous introduction to Shortest Paths, we learned that unweighted graphs can be solved with Breadth-First Search (BFS). However, when routes have varying costs (traffic delays, toll fees, network latency), we require a more advanced mechanism.

This is where Dijkstra's Algorithm shines. Let's take a deep dive into the inner workings of this legendary algorithm, understand its mathematical logic, and implement it in multiple programming languages.

1. The Core Concept: "Relaxation"

Dijkstra’s Algorithm works by maintaining a set of "currently known shortest distances" to every node, starting at Infinity for everything except the starting node (which is 0).

It then systematically evaluates paths. If it finds a cheaper way to reach a node than the currently recorded distance, it updates the record. This process of improving a known distance is formally called Edge Relaxation.

The Greedy Approach

Dijkstra is a Greedy Algorithm. At every intersection, it strictly evaluates the closest unvisited node. It assumes that if we always take the cheapest immediate option, we will organically discover the globally cheapest routes.

The Shortest Path Tree generated by Dijkstra's algorithm. Red paths indicate the optimal route to every single node originating from Node S.

2. Tracing the Algorithm (Step-by-Step)

Let's manually trace how the algorithm solves the graph illustrated above, starting from node S.

Notice how at Step 1, discovering the path S -> B -> A (Cost 5) was cheaper than the direct path S -> A (Cost 6). The algorithm successfully "relaxed" Node A from 6 down to 5!

3. Implementing Dijkstra in Python

In Python, we utilize the heapq module to act as our Priority Queue. This ensures that extracting the minimum-cost node is lightning fast.

import heapq

def dijkstra(graph, start):
    # Initialize tables
    distances = {node: float('inf') for node in graph}
    previous_nodes = {node: None for node in graph}
    distances[start] = 0
    # Priority Queue holds tuples of (current_cost, node)
    pq = [(0, start)]
    while pq:
        current_distance, current_node = heapq.heappop(pq)
        # If we pulled an outdated (more expensive) path from the heap, skip it
        if current_distance > distances[current_node]:
            continue
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            # Edge Relaxation!
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previous_nodes[neighbor] = current_node
                heapq.heappush(pq, (distance, neighbor))
    return distances, previous_nodes

4. Implementing Dijkstra in JavaScript

Unlike Python, JavaScript does not have a built-in Priority Queue structure. In technical interviews, you often have to mock one or use a basic array sort (which is slightly slower, but acceptable for smaller graphs).

function dijkstra(graph, start) {
  const distances = {};
  const previous = {};
  const pq = []; // Basic array to act as our queue

  // Initialize setup
  for (let vertex in graph) {
    distances[vertex] = vertex === start ? 0 : Infinity;
    previous[vertex] = null;
    pq.push({ node: vertex, priority: distances[vertex] });
  }
  while (pq.length > 0) {
    // Sort array to mock Min-Heap extraction (O(N log N))
    pq.sort((a, b) => a.priority - b.priority);
    let current = pq.shift().node;
    for (let neighbor in graph[current]) {
      let distance = distances[current] + graph[current][neighbor];
      if (distance < distances[neighbor]) {
        distances[neighbor] = distance;
        previous[neighbor] = current;
        pq.push({ node: neighbor, priority: distance });
      }
    }
  }
  return { distances, previous };
}
const graph = {
  'S': {'A': 6, 'B': 2},
  'A': {'C': 5},
  'B': {'A': 3, 'C': 1, 'E': 9},
  'C': {'D': 4, 'E': 5},
  'D': {},
  'E': {}
};
const result = dijkstra(graph, 'S').distances;
console.log("Minimum Distances:", result);
// Display output directly in the editor's web preview
if (typeof document !== 'undefined') {
  document.body.innerHTML = &lt;h3&gt;Shortest Paths from S:&lt;/h3&gt;&lt;pre&gt;${JSON.stringify(result, null, 2)}&lt;/pre&gt;;
}

5. Algorithmic Complexity

Because this algorithm traverses nodes and checks edges dynamically, understanding its complexity is highly dependent on the Priority Queue implementation.

• Time Complexity: O((V + E) * log(V)) if implemented securely with a standard Binary Min-Heap (like Python's implementation). The algorithm visits every vertex V, checks all corresponding edges E, and pushing/popping from the heap takes log(V) operations.
• Space Complexity: O(V) to store the distances hash map, the previous tracking table, and the size of the priority queue elements.