Dijkstra's Algorithm Single Source Shortest Path in DSA Javascript

Mental Model

Find the shortest path from one starting point to all other points by always choosing the closest unvisited point next.

Analogy: Imagine you are in a city and want to find the shortest way to every other city by always traveling to the nearest city you haven't visited yet.

Start: A (source)
Graph:
A --2--> B
A --5--> C
B --1--> C
C --3--> D
D --1--> E

Distances:
A: 0
B: ∞
C: ∞
D: ∞
E: ∞

Visited: none

Dry Run Walkthrough

Input: Graph with edges: A-B(2), A-C(5), B-C(1), C-D(3), D-E(1); start at A

Goal: Find shortest distances from A to all other nodes

Step 1: Start at A, set distance to 0, others to infinity

Distances: A[0], B[∞], C[∞], D[∞], E[∞]
Visited: {}
Current node: A

Why: We begin from the source with zero distance

Step 2: Update neighbors of A: B=2, C=5; mark A visited

Distances: A[0], B[2], C[5], D[∞], E[∞]
Visited: {A}
Current node: B (closest unvisited)

Why: We found shorter paths to B and C through A

Step 3: Update neighbors of B: C=min(5, 2+1=3)=3; mark B visited

Distances: A[0], B[2], C[3], D[∞], E[∞]
Visited: {A, B}
Current node: C (closest unvisited)

Why: Found a shorter path to C through B

Step 4: Update neighbors of C: D=3+3=6; mark C visited

Distances: A[0], B[2], C[3], D[6], E[∞]
Visited: {A, B, C}
Current node: D (closest unvisited)

Why: Set distance to D through C

Step 5: Update neighbors of D: E=6+1=7; mark D visited

Distances: A[0], B[2], C[3], D[6], E[7]
Visited: {A, B, C, D}
Current node: E (closest unvisited)

Why: Set distance to E through D

Step 6: Mark E visited; all nodes visited, algorithm ends

Distances: A[0], B[2], C[3], D[6], E[7]
Visited: {A, B, C, D, E}
Current node: none

Why: All nodes processed, shortest paths found

Result:

Final distances:
A -> 0
B -> 2
C -> 3
D -> 6
E -> 7

Annotated Code

DSA Javascript

class Graph {
  constructor() {
    this.nodes = new Set();
    this.adjList = new Map();
  }

  addNode(node) {
    this.nodes.add(node);
    if (!this.adjList.has(node)) {
      this.adjList.set(node, []);
    }
  }

  addEdge(src, dest, weight) {
    this.adjList.get(src).push({ node: dest, weight });
  }
}

function dijkstra(graph, start) {
  const distances = {};
  const visited = new Set();
  // Initialize distances
  graph.nodes.forEach(node => {
    distances[node] = Infinity;
  });
  distances[start] = 0;

  while (visited.size !== graph.nodes.size) {
    // Pick unvisited node with smallest distance
    let currentNode = null;
    let smallestDistance = Infinity;
    for (const node of graph.nodes) {
      if (!visited.has(node) && distances[node] < smallestDistance) {
        smallestDistance = distances[node];
        currentNode = node;
      }
    }

    if (currentNode === null) {
      break; // Remaining nodes are unreachable
    }

    // Update distances to neighbors
    for (const neighbor of graph.adjList.get(currentNode)) {
      if (!visited.has(neighbor.node)) {
        const newDist = distances[currentNode] + neighbor.weight;
        if (newDist < distances[neighbor.node]) {
          distances[neighbor.node] = newDist;
        }
      }
    }

    visited.add(currentNode);
  }

  return distances;
}

// Driver code
const graph = new Graph();
['A', 'B', 'C', 'D', 'E'].forEach(node => graph.addNode(node));
graph.addEdge('A', 'B', 2);
graph.addEdge('A', 'C', 5);
graph.addEdge('B', 'C', 1);
graph.addEdge('C', 'D', 3);
graph.addEdge('D', 'E', 1);

const distances = dijkstra(graph, 'A');
for (const node of ['A', 'B', 'C', 'D', 'E']) {
  console.log(`${node} -> ${distances[node]}`);
}

distances[start] = 0;

Set starting node distance to zero

for (const node of graph.nodes) { if (!visited.has(node) && distances[node] < smallestDistance) { smallestDistance = distances[node]; currentNode = node; } }

Select unvisited node with smallest known distance

const newDist = distances[currentNode] + neighbor.weight; if (newDist < distances[neighbor.node]) { distances[neighbor.node] = newDist; }

Update neighbor distances if shorter path found

visited.add(currentNode);

Mark current node as visited to avoid revisiting

Output

A -> 0

B -> 2

C -> 3

D -> 6

E -> 7

Complexity Analysis

Time: O(V^2) because for each node we scan all nodes to find the closest unvisited one

Space: O(V + E) because we store all nodes and edges in adjacency list and distances

vs Alternative: Using a priority queue can reduce time to O((V + E) log V) by efficiently selecting the closest node

Edge Cases

Graph with unreachable nodes

Distances remain Infinity for unreachable nodes

DSA Javascript

if (currentNode === null) { break; // Remaining nodes are unreachable }

Graph with single node

Distance to itself is zero, algorithm ends quickly

DSA Javascript

distances[start] = 0;

Graph with zero-weight edges

Algorithm correctly updates distances including zero weights

DSA Javascript

const newDist = distances[currentNode] + neighbor.weight;

When to Use This Pattern

When you need shortest paths from one point to all others in a weighted graph without negative edges, use Dijkstra's algorithm because it efficiently finds minimal distances step by step.

Common Mistakes

Mistake: Not updating distances when a shorter path is found
Fix: Add a check to update distances only if new distance is smaller than current

Mistake: Visiting nodes multiple times causing infinite loops
Fix: Keep a visited set and mark nodes visited after processing

Mistake: Using Dijkstra on graphs with negative edges
Fix: Use algorithms like Bellman-Ford for graphs with negative weights

Summary

Finds shortest distances from one start node to all others in a weighted graph without negative edges.

Use when you need shortest paths in graphs with non-negative weights.

Always pick the closest unvisited node next and update neighbors to find shortest paths.

Practice

1. What is the main purpose of Dijkstra's Algorithm in graph theory?

easy

A. To sort vertices in topological order

B. To find the maximum flow in a network

C. To detect cycles in a graph

D. To find the shortest path from a single source to all other vertices

Solution

1. Step 1: Understand the algorithm's goal

   Dijkstra's Algorithm is designed to find the shortest paths from one starting point (source) to all other points in a graph with non-negative edge weights.

2. Step 2: Compare with other graph algorithms

   Other algorithms like max flow or cycle detection serve different purposes, so they do not match Dijkstra's goal.

3. Final Answer:

   To find the shortest path from a single source to all other vertices -> Option D

4. Quick Check:

   Shortest path from one source = To find the shortest path from a single source to all other vertices [OK]

Hint: Dijkstra finds shortest paths from one start point [OK]

Common Mistakes:

• Confusing Dijkstra with max flow algorithms
• Thinking it detects cycles
• Assuming it sorts vertices

2. Which of the following is the correct way to initialize the distance array in Dijkstra's Algorithm in JavaScript?

easy

A. const dist = new Array(n).fill(Infinity); dist[source] = 0;

B. const dist = Array(n).fill(0); dist[source] = Infinity;

C. const dist = new Array(n).fill(null); dist[source] = 0;

D. const dist = new Array(n).fill(-1); dist[source] = 0;

Solution

1. Step 1: Understand distance initialization

   Distances to all nodes except the source should start as Infinity to represent unknown paths, and the source distance is 0.

2. Step 2: Check each option

   const dist = new Array(n).fill(Infinity); dist[source] = 0; correctly sets all distances to Infinity and source to 0. Others either set wrong initial values or invert source distance.

3. Final Answer:

   const dist = new Array(n).fill(Infinity); dist[source] = 0; -> Option A

4. Quick Check:

   Distance array starts with Infinity except source = const dist = new Array(n).fill(Infinity); dist[source] = 0; [OK]

Hint: Start distances as Infinity, source as 0 [OK]

Common Mistakes:

• Setting source distance to Infinity
• Using 0 for all distances initially
• Using null or -1 incorrectly

3. Consider the following JavaScript code snippet implementing part of Dijkstra's Algorithm. What will be the output of the distance array after running this code?

const graph = {
  0: [{node:1, weight:4}, {node:2, weight:1}],
  1: [{node:3, weight:1}],
  2: [{node:1, weight:2}, {node:3, weight:5}],
  3: []
};
const dist = [0, Infinity, Infinity, Infinity];
const visited = new Set();

function dijkstra() {
  while (visited.size < 4) {
    let u = -1;
    let minDist = Infinity;
    for (let i = 0; i < 4; i++) {
      if (!visited.has(i) && dist[i] < minDist) {
        minDist = dist[i];
        u = i;
      }
    }
    visited.add(u);
    for (const neighbor of graph[u]) {
      if (dist[u] + neighbor.weight < dist[neighbor.node]) {
        dist[neighbor.node] = dist[u] + neighbor.weight;
      }
    }
  }
}
dijkstra();
console.log(dist);

medium

A. [0, 4, 1, 6]

B. [0, 3, 1, 4]

C. [0, 2, 1, 3]

D. [0, 5, 1, 7]

Solution

1. Step 1: Trace initial distances and first iteration

   Start dist = [0, Infinity, Infinity, Infinity]. Pick node 0 (dist=0). Update neighbors: node 1 = 4, node 2 = 1.

2. Step 2: Next iterations and updates

   Pick node 2 (dist=1). Update node 1: min(4, 1+2=3) = 3; node 3: min(Infinity, 1+5=6) = 6. Pick node 1 (dist=3). Update node 3: min(6, 3+1=4) = 4. Pick node 3 (dist=4). No neighbors.

3. Final Answer:

   [0, 3, 1, 4] -> Option B

4. Quick Check:

   Distances after updates = [0, 3, 1, 4] [OK]

Hint: Pick unvisited node with smallest dist, update neighbors [OK]

Common Mistakes:

• Not updating distances correctly
• Choosing wrong next node
• Ignoring neighbor updates

4. The following code snippet is intended to implement Dijkstra's Algorithm but contains a bug. What is the bug?

const dist = new Array(n).fill(Infinity);
dist[source] = 0;
const visited = new Set();

while (visited.size < n) {
  let u = -1;
  let minDist = Infinity;
  for (let i = 0; i < n; i++) {
    if (dist[i] < minDist) {
      minDist = dist[i];
      u = i;
    }
  }
  visited.add(u);
  for (const neighbor of graph[u]) {
    if (dist[u] + neighbor.weight < dist[neighbor.node]) {
      dist[neighbor.node] = dist[u] + neighbor.weight;
    }
  }
}

medium

A. The visited set is not updated inside the loop

B. The distance array is not initialized correctly

C. The code does not check if node i is already visited before selecting u

D. The neighbor weights are not added to dist[u]

Solution

1. Step 1: Analyze node selection loop

   The loop selects node u with smallest dist[i] but does not check if i is already visited, so it may pick visited nodes again.

2. Step 2: Understand impact of missing visited check

   Without skipping visited nodes, the algorithm can loop incorrectly or update distances wrongly, breaking correctness.

3. Final Answer:

   The code does not check if node i is already visited before selecting u -> Option C

4. Quick Check:

   Must skip visited nodes when picking u = The code does not check if node i is already visited before selecting u [OK]

Hint: Always skip visited nodes when choosing next node [OK]

Common Mistakes:

• Forgetting to check visited nodes in selection
• Incorrect distance initialization
• Not updating visited set

5. You have a weighted graph with 5 nodes (0 to 4). The edges are:

• 0 -> 1 (2)
• 0 -> 2 (4)
• 1 -> 2 (1)
• 1 -> 3 (7)
• 2 -> 4 (3)
• 3 -> 4 (1)

Using Dijkstra's Algorithm from source node 0, what is the shortest distance to node 4?

hard

A. 6

B. 7

C. 8

D. 5

Solution

1. Step 1: Trace shortest paths from node 0

   Start dist: 0=0, others=Infinity. From 0: dist[1]=2, dist[2]=4.

2. Step 2: Update distances via neighbors

   From 1: dist[2]=min(4,2+1=3)=3, dist[3]=2+7=9. From 2: dist[4]=3+3=6. From 3: dist[4]=min(6,9+1=10)=6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Shortest distance to node 4 = 6 [OK]

Hint: Check all paths, pick minimum sum of weights [OK]

Common Mistakes:

• Ignoring shorter path through node 2
• Adding wrong edge weights
• Not updating distances properly