Dijkstra's Algorithm Single Source Shortest Path in DSA C++

Mental Model

Find the shortest path from one starting point to all other points by always choosing the closest unvisited point next.

Analogy: Imagine you are in a city and want to find the shortest way to every other city by always traveling to the nearest city you haven't visited yet.

Start: S
Graph:
S --2--> A --3--> B
|         |
4         1
|         |
C <-------

S: start node
Edges show distances

Dry Run Walkthrough

Input: Graph with nodes S, A, B, C and edges: S->A=2, S->C=4, A->B=3, A->C=1; start node S

Goal: Find shortest distances from S to all nodes

Step 1: Initialize distances: S=0, others=∞; mark all unvisited

Distances: S=0, A=∞, B=∞, C=∞; Unvisited: {S, A, B, C}

Why: We start knowing distance to start node is zero and others unknown

Step 2: Pick unvisited node with smallest distance: S=0; visit neighbors A and C

Update distances: A=min(∞,0+2)=2, C=min(∞,0+4)=4; Unvisited: {A, B, C}

Why: From S, we can reach A and C with distances 2 and 4

Step 3: Pick next closest unvisited node: A=2; visit neighbors B and C

Update distances: B=min(∞,2+3)=5, C=min(4,2+1)=3; Unvisited: {B, C}

Why: From A, we can reach B and possibly improve C's distance

Step 4: Pick next closest unvisited node: C=3; no neighbors to update

Distances unchanged: B=5; Unvisited: {B}

Why: C's neighbors already have shorter or equal distances

Step 5: Pick last unvisited node: B=5; no neighbors to update

All nodes visited; Distances: S=0, A=2, B=5, C=3

Why: All shortest distances found

Result:

S=0 -> A=2 -> C=3 -> B=5

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;

class Graph {
public:
    int V;
    vector<vector<pair<int,int>>> adj;

    Graph(int vertices) {
        V = vertices;
        adj.resize(V);
    }

    void addEdge(int u, int v, int w) {
        adj[u].push_back({v, w});
    }

    void dijkstra(int src) {
        vector<int> dist(V, numeric_limits<int>::max());
        dist[src] = 0; // start node distance zero

        using pii = pair<int,int>;
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        pq.push({0, src}); // distance, node

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

            if (currDist > dist[u]) continue; // skip outdated entry

            for (auto &edge : adj[u]) {
                int v = edge.first;
                int weight = edge.second;

                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight; // update shorter distance
                    pq.push({dist[v], v}); // push updated distance
                }
            }
        }

        for (int i = 0; i < V; i++) {
            cout << "Distance from node " << src << " to node " << i << " is " << dist[i] << "\n";
        }
    }
};

int main() {
    Graph g(4);
    g.addEdge(0, 1, 2); // S->A
    g.addEdge(0, 3, 4); // S->C
    g.addEdge(1, 2, 3); // A->B
    g.addEdge(1, 3, 1); // A->C

    g.dijkstra(0); // start from S (node 0)
    return 0;
}

dist[src] = 0; // start node distance zero

Initialize start node distance to zero

pq.push({0, src}); // distance, node

Add start node to priority queue with distance zero

if (currDist > dist[u]) continue; // skip outdated entry

Ignore entries with longer distances than current best

if (dist[u] + weight < dist[v]) {

Check if new path to neighbor is shorter

dist[v] = dist[u] + weight; // update shorter distance

Update neighbor distance with shorter path

pq.push({dist[v], v}); // push updated distance

Add neighbor with updated distance to priority queue

Output

Distance from node 0 to node 0 is 0

Distance from node 0 to node 1 is 2

Distance from node 0 to node 2 is 5

Distance from node 0 to node 3 is 3

Complexity Analysis

Time: O(E log V) because each edge is checked and priority queue operations take log V time

Space: O(V + E) for storing graph and distance arrays

vs Alternative: Compared to Bellman-Ford O(VE), Dijkstra is faster on graphs with non-negative weights

Edge Cases

Graph with no edges

Distances to all nodes except start remain infinite

DSA C++

dist[src] = 0; // start node distance zero

Graph with single node

Distance to itself is zero, no other nodes to update

DSA C++

dist[src] = 0; // start node distance zero

Graph with unreachable nodes

Distances to unreachable nodes remain infinite

DSA C++

if (currDist > dist[u]) continue; // skip outdated entry

When to Use This Pattern

When asked to find shortest paths from one node to all others in a graph with non-negative weights, use Dijkstra's algorithm because it efficiently finds minimum distances using a priority queue.

Common Mistakes

Mistake: Not updating distances when a shorter path is found
Fix: Add condition to update distance and push new pair to priority queue

Mistake: Not skipping outdated entries in priority queue
Fix: Add check to continue if current distance is greater than stored distance

Summary

Finds shortest distances from one start node to all others in a weighted graph with non-negative edges.

Use when you need efficient shortest path calculations from a single source in graphs without negative weights.

Always pick the closest unvisited node next and update neighbors to find shortest paths step by step.

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