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

Dijkstra's Algorithm Single Source Shortest Path

📖 Scenario: You are working as a city planner. You have a map of intersections connected by roads with different lengths. You want to find the shortest path from a starting intersection to all other intersections.

🎯 Goal: Build a program that uses Dijkstra's algorithm to find the shortest distance from a given start intersection to every other intersection in the city.

📋 What You'll Learn

Create a graph using adjacency lists with exact edges and weights

Define a variable for the number of intersections

Implement Dijkstra's algorithm using a priority queue

Print the shortest distances from the start intersection to all others

💡 Why This Matters

🌍 Real World

City planners and GPS navigation systems use shortest path algorithms like Dijkstra's to find the quickest routes between locations.

💼 Career

Understanding Dijkstra's algorithm is important for software engineers working on mapping, routing, network optimization, and logistics applications.

1

Create the graph with edges and weights

Create an integer variable V and set it to 5 for the number of intersections. Then create an adjacency list called graph as a vector of vectors of pairs of integers. Add these exact edges with weights to graph: from 0 to 1 with weight 10, from 0 to 4 with weight 5, from 1 to 2 with weight 1, from 1 to 4 with weight 2, from 2 to 3 with weight 4, from 3 to 0 with weight 7, from 3 to 2 with weight 6, from 4 to 1 with weight 3, from 4 to 2 with weight 9, and from 4 to 3 with weight 2.

DSA C++

#include 
#include 
#include 
#include 
#include 

using namespace std;

int main() {
    // Create variable V and adjacency list graph
    // Add edges with weights to graph
    // Your code here

Hint

Use vector>> graph(V); to create the adjacency list. Use graph[u].push_back({v, weight}); to add edges.

2

Set the start intersection

Create an integer variable called start and set it to 0 to represent the starting intersection.

DSA C++

#include 
#include 
#include 
#include 
#include 

using namespace std;

int main() {
    int V = 5;
    vector>> graph(V);
    graph[0].push_back({1, 10});
    graph[0].push_back({4, 5});
    graph[1].push_back({2, 1});
    graph[1].push_back({4, 2});
    graph[2].push_back({3, 4});
    graph[3].push_back({0, 7});
    graph[3].push_back({2, 6});
    graph[4].push_back({1, 3});
    graph[4].push_back({2, 9});
    graph[4].push_back({3, 2});
    // Create variable start and set to 0
    // Your code here

Hint

Just write int start = 0; to set the starting intersection.

3

Implement Dijkstra's algorithm

Create a vector of integers called dist with size V and initialize all values to INT_MAX. Set dist[start] to 0. Use a priority queue called pq of pairs of integers to store distances and nodes. Push {0, start} into pq. Then use a while loop that runs while pq is not empty. Inside the loop, pop the top element into current and u. If current is greater than dist[u], continue. Otherwise, for each neighbor v and weight w in graph[u], if dist[u] + w is less than dist[v], update dist[v] and push {dist[v], v} into pq.

DSA C++

#include 
#include 
#include 
#include 
#include 

using namespace std;

int main() {
    int V = 5;
    vector>> graph(V);
    graph[0].push_back({1, 10});
    graph[0].push_back({4, 5});
    graph[1].push_back({2, 1});
    graph[1].push_back({4, 2});
    graph[2].push_back({3, 4});
    graph[3].push_back({0, 7});
    graph[3].push_back({2, 6});
    graph[4].push_back({1, 3});
    graph[4].push_back({2, 9});
    graph[4].push_back({3, 2});
    int start = 0;
    // Implement Dijkstra's algorithm here
    // Your code here

Hint

Use a priority queue to always pick the closest unvisited node. Update distances if a shorter path is found.

4

Print the shortest distances

Use a for loop with variable i from 0 to V - 1. Inside the loop, print "Distance from " followed by start, " to ", i, " is ", and dist[i] on a new line.

DSA C++

#include 
#include 
#include 
#include 
#include 

using namespace std;

int main() {
    int V = 5;
    vector>> graph(V);
    graph[0].push_back({1, 10});
    graph[0].push_back({4, 5});
    graph[1].push_back({2, 1});
    graph[1].push_back({4, 2});
    graph[2].push_back({3, 4});
    graph[3].push_back({0, 7});
    graph[3].push_back({2, 6});
    graph[4].push_back({1, 3});
    graph[4].push_back({2, 9});
    graph[4].push_back({3, 2});
    int start = 0;

    vector dist(V, INT_MAX);
    dist[start] = 0;
    priority_queue, vector>, greater>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int current = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (current > 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});
            }
        }
    }

    // Print shortest distances
    // Your code here

Hint

Use a simple for loop and cout to print each distance line by line.

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