Dijkstra's Algorithm Single Source Shortest Path in DSA Javascript - Deep Dive

Overview - Dijkstra's Algorithm Single Source Shortest Path

What is it?

Dijkstra's Algorithm finds the shortest path from one starting point to all other points in a network or map. It works by exploring the closest points first and updating the shortest known distances step-by-step. This helps find the quickest way to reach every destination from the start. It is widely used in maps, routing, and network analysis.

Why it matters

Without Dijkstra's Algorithm, finding the shortest routes in complex networks would be slow and inefficient, making navigation apps, delivery services, and network routing unreliable or very slow. It solves the problem of quickly finding the best path in a way that computers can handle easily. This impacts daily life by enabling fast travel directions and efficient data flow.

Where it fits

Before learning Dijkstra's Algorithm, you should understand graphs, nodes, edges, and basic data structures like arrays and priority queues. After mastering it, you can explore more advanced shortest path algorithms like A* or Bellman-Ford, and graph optimization techniques.

Mental Model

Core Idea

Dijkstra's Algorithm grows the shortest path tree by always choosing the closest unvisited node and updating paths until all nodes have the shortest known distance from the start.

Think of it like...

Imagine you are in a city and want to visit all other neighborhoods starting from your home. You always pick the closest neighborhood you haven't visited yet, then update your knowledge of how far other neighborhoods are based on this new information.

Start Node
  │
  ▼
[Closest Unvisited Node] -> Update distances to neighbors
  │
  ▼
Repeat until all nodes visited

Graph example:

  (A)
  / \
5/   \1
 /     \
(B)---2--(C)

Distances updated stepwise from A.

Build-Up - 7 Steps

1

Foundation

Understanding Graphs and Weights

Concept: Graphs are made of points (nodes) connected by lines (edges) that can have numbers (weights) showing distance or cost.

A graph is a collection of nodes connected by edges. Each edge can have a weight representing distance or cost. For example, in a map, nodes are places and edges are roads with lengths. Understanding this helps us find shortest paths.

Result

You can represent a network as nodes and weighted edges, ready for pathfinding.

Knowing how to represent problems as weighted graphs is the first step to applying shortest path algorithms.

2

Foundation

What is Shortest Path Problem?

Concept: The shortest path problem asks: what is the minimum total weight to get from one node to another?

Given a start node, the goal is to find the path to each other node that has the smallest sum of edge weights. This is like finding the quickest route on a map.

Result

You understand the goal: minimize total travel cost from start to all nodes.

Framing the problem clearly helps in choosing the right algorithm to solve it.

3

Intermediate

Dijkstra's Algorithm Step-by-Step

🤔Before reading on: do you think Dijkstra updates all nodes at once or one node at a time? Commit to your answer.

Concept: Dijkstra's Algorithm picks the closest unvisited node, updates distances to neighbors, and repeats until all nodes are visited.

1. Start with the source node, set its distance to 0, others to infinity. 2. Pick the unvisited node with the smallest distance. 3. For each neighbor, calculate new distance through this node. 4. If new distance is smaller, update it. 5. Mark the node visited. 6. Repeat until all nodes visited.

Result

You get the shortest distance from the start to every node in the graph.

Understanding the greedy choice of the closest node ensures the algorithm finds the shortest paths efficiently.

4

Intermediate

Using Priority Queue for Efficiency

🤔Before reading on: do you think scanning all nodes to find the closest is fast or slow? Commit to your answer.

Concept: A priority queue helps quickly find the closest unvisited node, improving speed from scanning all nodes each time.

Instead of checking all nodes, use a priority queue that always gives the node with the smallest distance. When distances update, push neighbors into the queue. This reduces time from O(V^2) to O((V+E) log V) where V is nodes and E is edges.

Result

The algorithm runs much faster on large graphs.

Knowing how data structures like priority queues optimize algorithms is key to practical performance.

5

Intermediate

Implementing Dijkstra in JavaScript

🤔Before reading on: do you think the algorithm needs to store paths or just distances? Commit to your answer.

Concept: The algorithm tracks shortest distances and optionally the path by remembering previous nodes.

```javascript function dijkstra(graph, start) { const distances = {}; const visited = new Set(); const pq = new MinPriorityQueue(); const previous = {}; for (const node in graph) { distances[node] = Infinity; previous[node] = null; } distances[start] = 0; pq.enqueue(start, 0); while (!pq.isEmpty()) { const { element: current } = pq.dequeue(); if (visited.has(current)) continue; visited.add(current); for (const neighbor in graph[current]) { const newDist = distances[current] + graph[current][neighbor]; if (newDist < distances[neighbor]) { distances[neighbor] = newDist; previous[neighbor] = current; pq.enqueue(neighbor, newDist); } } } return { distances, previous }; } ``` Here, graph is an object with nodes as keys and neighbor-weight pairs as values.

Result

You can run Dijkstra's Algorithm and get shortest distances and paths.

Implementing the algorithm solidifies understanding and shows how data structures work together.

6

Advanced

Handling Graphs with Negative Edges

🤔Before reading on: do you think Dijkstra works correctly with negative edge weights? Commit to your answer.

Concept: Dijkstra's Algorithm assumes all edge weights are non-negative; negative edges break its logic.

If a graph has negative edges, Dijkstra can give wrong answers because it assumes once a node's shortest distance is found, it won't improve. Negative edges can reduce distances later, violating this. For such graphs, algorithms like Bellman-Ford are used.

Result

You know when not to use Dijkstra and choose alternatives.

Recognizing algorithm assumptions prevents incorrect use and bugs in real applications.

7

Expert

Optimizations and Real-World Tweaks

🤔Before reading on: do you think Dijkstra always explores all nodes? Commit to your answer.

Concept: In practice, Dijkstra can be optimized by stopping early or using heuristics to speed up specific queries.

For example, if you only want the shortest path to one target, you can stop once that node is visited. Also, bidirectional search runs Dijkstra from start and target simultaneously to meet in the middle. Combining with heuristics leads to A* algorithm. These tweaks improve speed in large networks.

Result

You understand practical improvements beyond the textbook algorithm.

Knowing real-world optimizations helps build efficient systems and prepares for advanced algorithms.

Under the Hood

Dijkstra's Algorithm maintains a set of nodes with known shortest distances and a priority queue to pick the next closest node. It updates neighbors' distances only if a shorter path is found through the current node. Internally, it relies on the greedy property that once a node is visited, its shortest path is finalized because all edge weights are non-negative.

Why designed this way?

The algorithm was designed to efficiently solve shortest path problems without exploring all paths exhaustively. The greedy approach and priority queue reduce unnecessary work. Alternatives like Bellman-Ford handle negative edges but are slower. Dijkstra balances speed and correctness for non-negative graphs.

┌─────────────┐
│ Initialize  │
│ distances 0 │
│ others ∞    │
└─────┬───────┘
      │
      ▼
┌─────────────┐
│ Pick node   │
│ with min    │
│ distance    │
└─────┬───────┘
      │
      ▼
┌─────────────┐
│ Update      │
│ neighbors   │
│ distances   │
└─────┬───────┘
      │
      ▼
┌─────────────┐
│ Mark node   │
│ visited     │
└─────┬───────┘
      │
      ▼
┌─────────────┐
│ Repeat until│
│ all visited │
└─────────────┘

Myth Busters - 3 Common Misconceptions

Quick: Does Dijkstra's Algorithm work correctly with negative edge weights? Commit to yes or no.

Common Belief: Dijkstra's Algorithm can handle any graph, including those with negative edge weights.

Reality: Dijkstra's Algorithm only works correctly if all edge weights are zero or positive. Negative edges can cause incorrect shortest paths.

Why it matters: Using Dijkstra on graphs with negative edges can lead to wrong routes, causing failures in navigation or network routing.

Quick: Does Dijkstra always find the shortest path to all nodes even if some nodes are unreachable? Commit to yes or no.

Common Belief: Dijkstra's Algorithm finds shortest paths to all nodes regardless of connectivity.

Reality: Dijkstra only finds shortest paths to nodes reachable from the start. Unreachable nodes remain at infinite distance.

Why it matters: Assuming all nodes are reachable can cause bugs or misinterpretation of results in disconnected graphs.

Quick: Is scanning all nodes to find the closest unvisited node efficient in large graphs? Commit to yes or no.

Common Belief: Checking all nodes each time to find the closest unvisited node is fast enough.

Reality: Scanning all nodes each time is slow (O(V^2)) for large graphs. Using a priority queue improves efficiency significantly.

Why it matters: Ignoring data structure optimization leads to slow algorithms that don't scale to real-world problems.

Expert Zone

1

Dijkstra's Algorithm can be adapted to work with dynamic graphs by updating distances incrementally without full recomputation.

2

The choice of priority queue implementation (binary heap, Fibonacci heap) affects theoretical and practical performance differently.

3

In dense graphs, simple arrays for distance selection can outperform complex heaps due to lower overhead.

When NOT to use

Do not use Dijkstra if the graph has negative edge weights; use Bellman-Ford instead. For very large graphs with heuristic knowledge, use A* algorithm. If only shortest path between two nodes is needed, bidirectional search or goal-directed search may be better.

Production Patterns

In real systems, Dijkstra is used in GPS navigation, network routing protocols like OSPF, and game AI pathfinding. Often combined with heuristics or run on simplified graphs for speed. Implementations handle large data with priority queues and early stopping.

Connections

Bellman-Ford Algorithm

Alternative algorithm for shortest paths that handles negative edges.

Understanding Dijkstra's limits helps appreciate Bellman-Ford's ability to detect negative cycles and handle negative weights.

Priority Queue Data Structure

Core data structure used to efficiently select the next node with smallest distance.

Mastering priority queues unlocks efficient implementations of many graph algorithms including Dijkstra.

Supply Chain Logistics

Both involve finding optimal routes and minimizing costs in networks.

Knowing shortest path algorithms helps model and optimize real-world logistics and delivery systems.

Common Pitfalls

#1 Using Dijkstra on graphs with negative edge weights.

Wrong approach:

const graph = { A: { B: -1 }, B: { C: 2 }, C: {} };
const result = dijkstra(graph, 'A');

Correct approach:

Use Bellman-Ford algorithm instead for graphs with negative edges.

Root cause:

Misunderstanding that Dijkstra requires non-negative weights to guarantee correctness.

#2 Scanning all nodes to find the closest unvisited node without a priority queue.

Wrong approach:

function dijkstra(graph, start) {
const distances = {};
const visited = new Set();
for (const node in graph) distances[node] = Infinity;
distances[start] = 0;
while (visited.size < Object.keys(graph).length) {
let closest = null;
let minDist = Infinity;
for (const node in distances) {
if (!visited.has(node) && distances[node] < minDist) {
minDist = distances[node];
closest = node;
}
}
visited.add(closest);
// update neighbors...
}
}

Correct approach:

Use a priority queue to select the closest node efficiently:
const pq = new MinPriorityQueue();
pq.enqueue(start, 0);
while (!pq.isEmpty()) {
const { element: current } = pq.dequeue();
if (visited.has(current)) continue;
visited.add(current);
// update neighbors and enqueue
}

Root cause:

Not using efficient data structures leads to slow performance on large graphs.

#3 Not updating the distance when a shorter path is found.

Wrong approach:

if (newDist >= distances[neighbor]) {
// do nothing
}

Correct approach:

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

Root cause:

Failing to update distances breaks the algorithm's correctness and leads to wrong shortest paths.

Key Takeaways

Dijkstra's Algorithm finds shortest paths from one start node to all others by always exploring the closest unvisited node next.

It requires all edge weights to be non-negative to guarantee correct results.

Using a priority queue is essential for efficient performance on large graphs.

The algorithm can be adapted and optimized for real-world use cases like early stopping and bidirectional search.

Understanding its assumptions and limits helps choose the right algorithm for different graph problems.

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