Dijkstra's Algorithm Single Source Shortest Path in DSA Javascript - Build from Scratch

Dijkstra's Algorithm Single Source Shortest Path

📖 Scenario: You are working on a navigation app that helps users find the shortest path from one location to all other locations on a map. The map is represented as a graph where locations are nodes and roads are edges with distances.

🎯 Goal: Build a program that uses Dijkstra's algorithm to find the shortest distance from a starting location to all other locations in the graph.

📋 What You'll Learn

Create a graph as an adjacency list with exact nodes and edges

Set a starting node for the shortest path calculation

Implement Dijkstra's algorithm core logic to find shortest paths

Print the shortest distances from the start node to all other nodes

💡 Why This Matters

🌍 Real World

Navigation apps, GPS devices, and mapping software use Dijkstra's algorithm to find shortest routes between locations.

💼 Career

Understanding Dijkstra's algorithm is essential for software engineers working on routing, logistics, network optimization, and game development.

1

Create the graph as an adjacency list

Create a variable called graph as an object representing the graph. Use these exact nodes and edges with distances: 'A': {'B': 4, 'C': 2}, 'B': {'A': 4, 'C': 5, 'D': 10}, 'C': {'A': 2, 'B': 5, 'D': 3}, 'D': {'B': 10, 'C': 3}.

DSA Javascript

// Your code here

Hint

Use an object where each key is a node and its value is another object with neighbors and distances.

2

Set the starting node

Create a variable called startNode and set it to the string 'A' as the starting point for the shortest path calculation.

DSA Javascript

const graph = {
  'A': {'B': 4, 'C': 2},
  'B': {'A': 4, 'C': 5, 'D': 10},
  'C': {'A': 2, 'B': 5, 'D': 3},
  'D': {'B': 10, 'C': 3}
};

// Your code here

Hint

Just assign the string 'A' to a variable named startNode.

3

Implement Dijkstra's algorithm core logic

Write a function called dijkstra that takes graph and startNode as parameters. Inside, create a distances object with all nodes set to Infinity except startNode set to 0. Use a visited set to track visited nodes. While there are unvisited nodes, pick the unvisited node with the smallest distance, update distances to its neighbors if shorter paths are found, and mark it visited. Return the distances object.

DSA Javascript

const graph = {
  'A': {'B': 4, 'C': 2},
  'B': {'A': 4, 'C': 5, 'D': 10},
  'C': {'A': 2, 'B': 5, 'D': 3},
  'D': {'B': 10, 'C': 3}
};

const startNode = 'A';

// Your code here

Hint

Use a loop to pick the closest unvisited node, update neighbors, and mark visited until all nodes are visited.

4

Print the shortest distances

Call the dijkstra function with graph and startNode, store the result in shortestDistances, and print shortestDistances using console.log.

DSA Javascript

const graph = {
  'A': {'B': 4, 'C': 2},
  'B': {'A': 4, 'C': 5, 'D': 10},
  'C': {'A': 2, 'B': 5, 'D': 3},
  'D': {'B': 10, 'C': 3}
};

const startNode = 'A';

function dijkstra(graph, startNode) {
  const distances = {};
  const visited = new Set();

  for (const node in graph) {
    distances[node] = Infinity;
  }
  distances[startNode] = 0;

  while (visited.size < Object.keys(graph).length) {
    let currentNode = null;
    let smallestDistance = Infinity;

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

    if (currentNode === null) {
      break;
    }

    for (const neighbor in graph[currentNode]) {
      if (!visited.has(neighbor)) {
        const newDistance = distances[currentNode] + graph[currentNode][neighbor];
        if (newDistance < distances[neighbor]) {
          distances[neighbor] = newDistance;
        }
      }
    }

    visited.add(currentNode);
  }

  return distances;
}

// Your code here

Hint

Call dijkstra with graph and startNode, save result, then print it.

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