Dijkstra's Algorithm Single Source Shortest Path in DSA C++ - 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 graph. 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 point from the start. It only works with graphs that have no negative distances.

Why it matters

Without Dijkstra's Algorithm, finding the shortest routes in maps, networks, or delivery paths would be slow and inefficient. It helps GPS devices, internet routing, and many real-world systems work fast and smart. Without it, we would waste time and resources traveling or sending data.

Where it fits

Before learning Dijkstra's, 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 Bellman-Ford or A* search.

Mental Model

Core Idea

Dijkstra's Algorithm grows the shortest path tree by always choosing the closest unvisited point and updating paths from there.

Think of it like...

Imagine you are in a city and want to find the quickest way to every other place. You start by checking the closest streets, then move outward, always picking the nearest unexplored street to update your best routes.

Start (S)
  |
  v
[Visited Nodes] ---(Edges with distances)---> [Unvisited Nodes]

Process:
1. Pick closest unvisited node
2. Update distances to neighbors
3. Mark node visited
4. Repeat until all nodes visited

Build-Up - 7 Steps

1

Foundation

Understanding Graphs and Distances

Concept: Graphs are made of points (nodes) connected by lines (edges) with distances (weights).

A graph is a collection of nodes connected by edges. Each edge has a weight representing distance or cost. For example, a map with cities as nodes and roads as edges with lengths as weights.

Result

You can represent real-world networks as graphs with weighted edges.

Knowing how to model problems as graphs with weights is the base for shortest path algorithms.

2

Foundation

Shortest Path Problem Setup

Concept: The goal is to find the minimum total distance from one start node to all others.

Given a start node, we want to find the shortest path to every other node. Initially, distances are unknown except zero for the start. We update these distances as we explore the graph.

Result

You understand the problem Dijkstra's Algorithm solves.

Framing the problem clearly helps understand why we update distances step by step.

3

Intermediate

Greedy Selection of Closest Node

🤔Before reading on: do you think picking any unvisited node or the closest unvisited node leads to correct shortest paths? Commit to your answer.

Concept: Always pick the unvisited node with the smallest known distance to explore next.

Dijkstra's Algorithm uses a greedy approach: it selects the closest unvisited node to the start. This ensures that when we pick a node, we have found the shortest path to it.

Result

The algorithm builds shortest paths in order of increasing distance from the start.

Choosing the closest node first guarantees that once a node is visited, its shortest path is final.

4

Intermediate

Updating Neighbor Distances

🤔Before reading on: do you think updating neighbors' distances only when a shorter path is found is necessary? Commit to your answer.

Concept: When visiting a node, update the distances of its neighbors if a shorter path is found through this node.

For each neighbor of the current node, calculate the distance through the current node. If this is less than the previously known distance, update it. This step spreads the shortest path information through the graph.

Result

Distances to neighbors get improved step by step, converging to shortest paths.

Updating neighbors only when shorter paths are found prevents unnecessary work and ensures correctness.

5

Intermediate

Using Priority Queue for Efficiency

🤔Before reading on: do you think scanning all nodes to find the closest unvisited node is efficient? Commit to your answer.

Concept: A priority queue helps quickly select the closest unvisited node without scanning all nodes each time.

Instead of searching all nodes, a priority queue stores nodes by their current shortest distance. Extracting the minimum distance node is fast, speeding up the algorithm.

Result

The algorithm runs efficiently even on large graphs.

Using the right data structure is key to making Dijkstra's Algorithm practical for real problems.

6

Advanced

Handling Graphs with No Negative Edges

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

Concept: Dijkstra's Algorithm assumes all edge weights are zero or positive to guarantee correctness.

If edges have negative weights, the greedy approach can fail because a shorter path might be found later. For such graphs, other algorithms like Bellman-Ford are needed.

Result

You know when Dijkstra's Algorithm applies and when it does not.

Understanding algorithm limits prevents incorrect use and wrong results.

7

Expert

Optimizations and Variants in Practice

🤔Before reading on: do you think Dijkstra's Algorithm always uses the same data structures and runs the same way in all systems? Commit to your answer.

Concept: Real-world systems optimize Dijkstra's Algorithm with different data structures and heuristics for speed and memory.

Variants include using Fibonacci heaps for faster priority queue operations or combining with heuristics (like A*). Also, bidirectional search runs Dijkstra from both start and end to meet in the middle.

Result

You see how Dijkstra's Algorithm adapts to complex, large-scale problems.

Knowing practical optimizations helps apply the algorithm effectively in production.

Under the Hood

Dijkstra's Algorithm maintains a set of visited nodes with known shortest distances. It uses a priority queue to pick the closest unvisited node. When a node is visited, it relaxes edges by updating neighbors' distances if a shorter path is found. This process repeats until all nodes are visited or the queue is empty.

Why designed this way?

The greedy approach was chosen because it guarantees shortest paths in graphs with non-negative weights. Using a priority queue reduces the time complexity from scanning all nodes repeatedly to logarithmic time per operation. Alternatives like Bellman-Ford handle negative edges but are slower.

┌───────────────┐
│ Start Node (S)│
└──────┬────────┘
       │
       ▼
┌───────────────┐       ┌───────────────┐
│Visited Nodes  │──────▶│Unvisited Nodes│
│(Known shortest│       │(Distances updated│
│ paths fixed)  │       │ as better paths │
└───────────────┘       │ are found)     │
                        └───────────────┘

Process:
1. Extract closest unvisited node from priority queue
2. Relax edges to neighbors
3. Update priority queue
4. Repeat

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.

Why it matters: Using it with negative edges can produce wrong shortest paths, causing failures in routing or planning.

Quick: Is the first path found to a node always the shortest? Commit to yes or no.

Common Belief: The first path found to a node is always the shortest path to that node.

Reality: Only when the node is selected as the closest unvisited node is its shortest path guaranteed; earlier paths may be longer and get updated.

Why it matters: Assuming the first path is shortest can lead to incorrect distance updates and wrong final results.

Quick: Does Dijkstra's Algorithm always find the shortest path to a single target faster than exploring all nodes? Commit to yes or no.

Common Belief: Dijkstra's Algorithm always quickly finds the shortest path to a single target without exploring the whole graph.

Reality: Dijkstra's Algorithm explores nodes in order of distance and may visit many nodes before reaching the target; it does not stop early unless modified.

Why it matters: Expecting early stopping can cause inefficient implementations or wrong assumptions about performance.

Expert Zone

1

Dijkstra's Algorithm's correctness depends on the priority queue always extracting the minimum distance node; lazy updates can cause subtle bugs.

2

In dense graphs, using a simple array instead of a priority queue can sometimes be faster due to lower overhead.

3

Bidirectional Dijkstra runs two simultaneous searches from start and target, reducing explored nodes but requires careful synchronization.

When NOT to use

Do not use Dijkstra's Algorithm if the graph has negative edge weights; use Bellman-Ford instead. For heuristic-driven shortest paths, use A* search. For very large graphs with dynamic changes, consider specialized algorithms like contraction hierarchies.

Production Patterns

In real systems, Dijkstra's Algorithm is used in GPS navigation, network routing protocols like OSPF, and game AI pathfinding. Implementations often combine it with heuristics or run it bidirectionally for speed.

Connections

Bellman-Ford Algorithm

Alternative shortest path algorithm that handles negative edges

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

Priority Queue Data Structure

Core data structure used to efficiently select the next node

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

Supply Chain Logistics

Real-world application of shortest path for cost and time optimization

Knowing how shortest path algorithms optimize routes helps improve delivery and resource planning in logistics.

Common Pitfalls

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

Wrong approach:

Run Dijkstra's Algorithm on a graph where some edges have negative weights without any modification.

Correct approach:

Use Bellman-Ford Algorithm for graphs with negative edge weights to correctly find shortest paths.

Root cause:

Misunderstanding that Dijkstra's Algorithm assumes non-negative weights for correctness.

#2 Not updating neighbor distances only when a shorter path is found.

Wrong approach:

Always update neighbor distances regardless of whether the new path is shorter:
if (new_distance > old_distance) {
distance[neighbor] = new_distance;
}

Correct approach:

Update neighbor distances only if the new path is shorter:
if (new_distance < old_distance) {
distance[neighbor] = new_distance;
}

Root cause:

Confusing the comparison operator leads to incorrect distance updates and wrong results.

#3 Scanning all nodes to find the closest unvisited node instead of using a priority queue.

Wrong approach:

For each step, loop through all nodes to find the minimum distance unvisited node, causing O(V^2) time complexity.

Correct approach:

Use a priority queue (min-heap) to extract the closest unvisited node in O(log V) time.

Root cause:

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

Key Takeaways

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

It requires all edge weights to be zero or positive to guarantee correct shortest paths.

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

Updating neighbor distances only when a shorter path is found ensures correctness and efficiency.

Understanding its limits and practical optimizations helps apply Dijkstra's Algorithm effectively in real-world systems.

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 distances from one starting point (source) to every other point 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:

   Dijkstra's Algorithm = shortest paths from source [OK]

Hint: Remember: Dijkstra finds shortest paths from one source [OK]

Common Mistakes:

• Confusing Dijkstra with algorithms for max flow
• 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 C++?

easy

A. vector<int> dist(n, -1); dist[source] = 0;

B. vector<int> dist(n, INT_MAX); dist[source] = 0;

C. vector<int> dist(n, 0); dist[source] = INT_MAX;

D. vector<int> dist(n); dist[source] = 0;

Solution

1. Step 1: Understand distance initialization

   Distances to all nodes except the source should start as infinity (or a very large number) to represent unknown distance.

2. Step 2: Check each option

   vector<int> dist(n, INT_MAX); dist[source] = 0; correctly sets all distances to INT_MAX and source distance to 0. Others either set wrong initial values or leave uninitialized.

3. Final Answer:

   vector<int> dist(n, INT_MAX); dist[source] = 0; -> Option B

4. Quick Check:

   Distance array initialized with INT_MAX except source = 0 [OK]

Hint: Initialize all distances to max except source zero [OK]

Common Mistakes:

• Setting all distances to zero initially
• Not setting source distance to zero
• Leaving distance array uninitialized

3. Consider the following graph edges and weights:

0 -> 1 (4), 0 -> 2 (1), 2 -> 1 (2), 1 -> 3 (1), 2 -> 3 (5)

If we run Dijkstra's Algorithm from source vertex 0, what is the shortest distance array after completion?

medium

A. [0, 3, 1, 4]

B. [0, 4, 1, 6]

C. [0, 2, 1, 3]

D. [0, 5, 1, 7]

Solution

1. Step 1: Initialize distances

   Start with dist = [0, INF, INF, INF]. Source 0 distance is 0.

2. Step 2: Relax edges step-by-step

   From 0: dist[1] = 4, dist[2] = 1. From 2: dist[1] = min(4, 1+2=3) = 3, dist[3] = 1+5=6. From 1: dist[3] = min(6, 3+1=4) = 4.

3. Final Answer:

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

4. Quick Check:

   Shortest distances from 0 = [0,3,1,4] [OK]

Hint: Update distances by relaxing edges with minimum sums [OK]

Common Mistakes:

• Not updating distance to vertex 1 via vertex 2
• Incorrectly summing edge weights
• Ignoring better paths found later

4. The following C++ code snippet for Dijkstra's Algorithm has a bug. What is the error?

vector<int> dist(n, INT_MAX);
dist[source] = 0;
priority_queue> pq;
pq.push({0, source});
while(!pq.empty()) {
  int u = pq.top().second;
  int d = pq.top().first;
  pq.pop();
  if(d > dist[u]) continue;
  for(auto &edge : graph[u]) {
    int v = edge.first;
    int w = edge.second;
    if(dist[u] + w < dist[v]) {
      dist[v] = dist[u] + w;
      pq.push({dist[v], v});
    }
  }
}

medium

A. priority_queue is max-heap by default (needs negative distances or greater comparator)

B. Distance array is not initialized correctly

C. The graph adjacency list is not iterated properly

D. The source distance is not set to zero

Solution

1. Step 1: Check priority queue usage

   In C++, priority_queue by default is max-heap. To get min-heap behavior for distances, distances should be pushed as negative or use greater comparator.

2. Step 2: Identify the bug

   The code pushes distances as positive values, so the smallest distance won't be on top, causing incorrect behavior.

3. Final Answer:

   priority_queue is max-heap by default (needs negative distances or greater comparator) -> Option A

4. Quick Check:

   Use negative distances or min-heap for correct priority queue [OK]

Hint: Use negative distances or min-heap to get smallest distance first [OK]

Common Mistakes:

• Ignoring priority queue ordering behavior
• Not setting source distance to zero
• Incorrect graph iteration

5. You have a weighted graph with 5 vertices and edges:

0->1(10), 0->4(5), 1->2(1), 2->3(4), 4->1(3), 4->2(9), 4->3(2), 3->0(7)

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

hard

A. 13

B. 15

C. 7

D. 18

Solution

1. Step 1: Initialize distances

   dist = [0, INF, INF, INF, INF]. Source 0 distance is 0.

2. Step 2: Relax edges step-by-step

   From 0: dist[1]=10, dist[4]=5. From 4: dist[1]=min(10,5+3=8)=8, dist[2]=min(INF,5+9=14)=14, dist[3]=min(INF,5+2=7)=7. From 1: dist[2]=min(14,8+1=9)=9. From 2: dist[3]=min(7,9+4=13)=7.

3. Step 3: Final shortest distance to vertex 3

   The shortest distance to vertex 3 is 7.

4. Final Answer:

   7 -> Option C

5. Quick Check:

   Shortest distance to vertex 3 = 7 [OK]

Hint: Relax edges in order, update distances with minimum sums [OK]

Common Mistakes:

• Not updating distances via vertex 4
• Ignoring better paths through intermediate vertices
• Confusing edge weights