Dijkstra's Algorithm Single Source Shortest Path in DSA Typescript - 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 paths step-by-step, always choosing the closest unvisited point next. This helps find the quickest way to reach every destination from the start. It is widely used in maps, routing, and network systems.

Why it matters

Without Dijkstra's Algorithm, finding the shortest routes in complex networks would be slow and error-prone. Imagine trying to find the fastest way home without a map or GPS; you'd waste time and effort. This algorithm makes navigation efficient and reliable, saving time and resources in real life and technology.

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 pathfinding algorithms like A* or Bellman-Ford, and graph optimization techniques.

Mental Model

Core Idea

Always pick the closest unvisited point and update paths until all shortest distances from the start are found.

Think of it like...

Imagine you are delivering packages in a city. You always go to the nearest house you haven't visited yet, updating your best route as you go, until all packages are delivered in the shortest total travel time.

Start (S)
  |
  v
[Node A] --5--> [Node B]
  |              |
  2              1
  |              |
[Node C] --3--> [Node D]

Distances updated step-by-step, always choosing the closest next node.

Build-Up - 6 Steps

1

Foundation

Understanding Graphs and Paths

Concept: Learn what graphs are and how paths connect nodes with distances.

A graph is a collection of points called nodes connected by lines called edges. Each edge can have a distance or cost. A path is a sequence of edges connecting nodes. For example, a map of cities connected by roads is a graph where roads have lengths.

Result

You can visualize networks and understand how nodes connect with distances.

Understanding graphs is essential because Dijkstra's Algorithm works by exploring these connections to find shortest paths.

2

Foundation

Basics of Distance Tracking

Concept: Learn how to keep track of the shortest known distance to each node.

We start by setting the distance to the start node as zero and all others as infinity (unknown). As we explore, we update these distances when we find shorter paths. This tracking helps us know the best route so far to each node.

Result

You can represent and update shortest distances during pathfinding.

Tracking distances lets the algorithm remember the best routes found so far, preventing unnecessary re-checking.

3

Intermediate

Using a Priority Queue for Efficiency

🤔Before reading on: do you think checking nodes in any order works as well as always picking the closest? Commit to your answer.

Concept: Introduce a priority queue to always pick the closest unvisited node next.

A priority queue is a special list that always gives you the smallest distance node first. This ensures the algorithm explores nodes in order of increasing distance, which is key to finding shortest paths efficiently.

Result

The algorithm runs faster by avoiding unnecessary checks and focusing on closest nodes first.

Using a priority queue is what makes Dijkstra's Algorithm efficient and practical for large graphs.

4

Intermediate

Relaxation: Updating Shortest Paths

🤔Before reading on: do you think once a node's distance is set, it can never be improved? Commit to yes or no.

Concept: Learn the relaxation step where distances to neighbors are updated if a shorter path is found.

For each neighbor of the current node, we check if going through the current node offers a shorter path. If yes, we update the neighbor's distance and add it to the priority queue for future exploration.

Result

Distances get progressively shorter and more accurate until the shortest paths are found.

Relaxation is the core operation that improves path estimates and leads to the final shortest distances.

5

Advanced

Implementing Dijkstra's Algorithm in TypeScript

🤔Before reading on: do you think the algorithm needs to revisit nodes multiple times or just once? Commit to your answer.

Concept: Combine all concepts into a runnable TypeScript code example using a priority queue and relaxation.

```typescript class PriorityQueue { private items: {node: T; priority: number}[] = []; enqueue(node: T, priority: number) { this.items.push({node, priority}); this.items.sort((a, b) => a.priority - b.priority); } dequeue(): T | undefined { return this.items.shift()?.node; } isEmpty(): boolean { return this.items.length === 0; } } function dijkstra(graph: Map>, start: string): Map { const distances = new Map(); const pq = new PriorityQueue(); for (const node of graph.keys()) { distances.set(node, Infinity); } distances.set(start, 0); pq.enqueue(start, 0); while (!pq.isEmpty()) { const current = pq.dequeue()!; const currentDist = distances.get(current)!; const neighbors = graph.get(current); if (!neighbors) continue; for (const [neighbor, weight] of neighbors.entries()) { const distance = currentDist + weight; if (distance < distances.get(neighbor)!) { distances.set(neighbor, distance); pq.enqueue(neighbor, distance); } } } return distances; } // Example graph const graph = new Map>(); graph.set('A', new Map([['B', 5], ['C', 2]])); graph.set('B', new Map([['D', 1]])); graph.set('C', new Map([['D', 3]])); graph.set('D', new Map()); const result = dijkstra(graph, 'A'); console.log(Object.fromEntries(result)); ```

Result

{"A":0,"B":5,"C":2,"D":5}

Seeing the full code connects theory to practice, showing how all parts work together to find shortest paths.

6

Expert

Handling Graphs with Negative Edges and Optimization

🤔Before reading on: do you think Dijkstra's Algorithm works correctly with negative edge weights? Commit to yes or no.

Concept: Understand why Dijkstra's Algorithm fails with negative edges and how to optimize it for large graphs.

Dijkstra's Algorithm assumes all edge weights are non-negative. Negative edges can cause it to miss shorter paths because it never revisits nodes with updated distances. For graphs with negative edges, algorithms like Bellman-Ford are used. Also, using a binary heap or Fibonacci heap instead of a simple sorted list for the priority queue improves performance on large graphs.

Result

You know when not to use Dijkstra and how to improve its efficiency in real systems.

Knowing the algorithm's limits prevents incorrect results and guides choosing the right tool for the problem.

Under the Hood

Dijkstra's Algorithm maintains a set of nodes with known shortest distances from the start. It uses a priority queue to pick the closest unvisited node, then updates distances to its neighbors if shorter paths are found (relaxation). This process repeats until all nodes are visited or reachable nodes are processed. Internally, it relies on updating a distance table and efficiently selecting the next node to explore.

Why designed this way?

The algorithm was designed by Edsger Dijkstra in 1956 to solve shortest path problems efficiently. It uses a greedy approach, always choosing the closest node next, which works because edge weights are non-negative. Alternatives like Bellman-Ford handle negative edges but are slower. The priority queue optimizes node selection, balancing speed and simplicity.

┌───────────────┐
│ Start Node (S)│
└──────┬────────┘
       │
       ▼
┌───────────────┐       ┌───────────────┐
│ Current Node  │──────▶│ Neighbor Node │
│ (closest)     │       │ (update dist) │
└──────┬────────┘       └──────┬────────┘
       │                       │
       │ Relax distances       │
       │                       │
       ▼                       ▼
┌───────────────┐       ┌───────────────┐
│ Priority Queue│◀──────│ Updated Nodes │
│ (next closest)│       │               │
└───────────────┘       └───────────────┘

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 works with any edge weights, including negative ones.

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 produce wrong results, leading to wrong decisions in routing or planning.

Quick: Once a node's shortest distance is set, can it be improved later? Commit to yes or no.

Common Belief: Once a node's distance is set, it never changes again.

Reality: Distances can be updated multiple times during the algorithm until the shortest path is confirmed when the node is visited.

Why it matters: Assuming distances never change can lead to skipping important updates and incorrect paths.

Quick: Is a simple list enough for the priority queue in large graphs? Commit to yes or no.

Common Belief: Any data structure works fine for the priority queue, even simple lists.

Reality: Using a simple list for the priority queue makes the algorithm slower on large graphs; efficient heaps improve performance significantly.

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

Expert Zone

1

Dijkstra's Algorithm can be optimized with different priority queue implementations like binary heaps or Fibonacci heaps for better performance.

2

In dense graphs, the overhead of priority queues might outweigh benefits, making simpler algorithms competitive.

3

The algorithm can be adapted to stop early when the shortest path to a specific target node is found, saving time.

When NOT to use

Avoid Dijkstra's Algorithm when graphs have negative edge weights; use Bellman-Ford instead. For very large graphs with dynamic changes, consider A* or specialized routing algorithms. If only shortest path to one target is needed, A* with heuristics is often faster.

Production Patterns

Dijkstra's Algorithm is used in GPS navigation to find shortest routes, in network routing protocols like OSPF, and in game development for pathfinding. It is often combined with heuristics or run on simplified graphs for speed.

Connections

Bellman-Ford Algorithm

Alternative algorithm for shortest paths that handles negative edges.

Understanding Dijkstra's limits helps appreciate Bellman-Ford's ability to handle negative weights at the cost of speed.

Priority Queues (Data Structures)

Core data structure used to efficiently select the next node to explore.

Mastering priority queues unlocks efficient implementations of many algorithms beyond Dijkstra.

Supply Chain Logistics

Both involve finding optimal routes to deliver goods efficiently.

Knowing how Dijkstra's Algorithm works deepens understanding of real-world logistics optimization problems.

Common Pitfalls

#1 Using Dijkstra's Algorithm on graphs with negative edge weights.

Wrong approach:

const graph = new Map([['A', new Map([['B', -5]])], ['B', new Map()]]);
const result = dijkstra(graph, 'A');
console.log(result);

Correct approach:

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

Root cause:

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

#2 Not updating distances during relaxation properly.

Wrong approach:

if (distance <= distances.get(neighbor)) {
// no update
}

Correct approach:

if (distance < distances.get(neighbor)) {
distances.set(neighbor, distance);
pq.enqueue(neighbor, distance);
}

Root cause:

Using <= instead of < prevents updating when a strictly shorter path is found.

#3 Using an unsorted list for the priority queue in large graphs.

Wrong approach:

class PriorityQueue {
enqueue(node, priority) { this.items.push({node, priority}); }
dequeue() { return this.items.shift().node; }
}

Correct approach:

Use a binary heap or sorted array to keep items ordered by priority for efficient dequeue.

Root cause:

Ignoring the importance of data structure efficiency leads to slow performance.

Key Takeaways

Dijkstra's Algorithm finds shortest paths by always exploring the closest unvisited node next.

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

A priority queue is essential for efficiently selecting the next node to process.

Relaxation updates distances to neighbors when shorter paths are found, refining the solution.

Understanding its limits and optimizations helps apply it correctly in real-world problems.