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
S --5--> B
A --1--> B
A --3--> C
B --2--> C

Distances:
S: 0
A: ∞
B: ∞
C: ∞

Visited: none

Dry Run Walkthrough

Input: Graph with nodes S, A, B, C and edges: S-A(2), S-B(5), A-B(1), A-C(3), B-C(2); 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[∞]; Visited: none

Why: Set starting point distance to zero and others unknown

Step 2: Pick unvisited node with smallest distance: S(0); visit S

Visited: S; Distances: S[0], A[∞], B[∞], C[∞]

Why: Start from source node

Step 3: Update neighbors of S: A=2, B=5

Distances: S[0], A[2], B[5], C[∞]; Visited: S

Why: Check direct paths from S

Step 4: Pick unvisited node with smallest distance: A(2); visit A

Visited: S, A; Distances: S[0], A[2], B[5], C[∞]

Why: Next closest node to explore

Step 5: Update neighbors of A: B=min(5, 2+1=3)=3, C=2+3=5

Distances: S[0], A[2], B[3], C[5]; Visited: S, A

Why: Found shorter path to B and new path to C

Step 6: Pick unvisited node with smallest distance: B(3); visit B

Visited: S, A, B; Distances: S[0], A[2], B[3], C[5]

Why: Next closest node to explore

Step 7: Update neighbors of B: C=min(5, 3+2=5)=5 (no change)

Distances: S[0], A[2], B[3], C[5]; Visited: S, A, B

Why: No shorter path to C found

Step 8: Pick unvisited node with smallest distance: C(5); visit C

Visited: S, A, B, C; Distances: S[0], A[2], B[3], C[5]

Why: All nodes visited, algorithm ends

Result:

Final distances: S[0] -> A[2] -> B[3] -> C[5]

Annotated Code

DSA C

#include <stdio.h>
#include <limits.h>
#include <stdbool.h>

#define V 4

int minDistance(int dist[], bool sptSet[]) {
    int min = INT_MAX, min_index = -1;
    for (int v = 0; v < V; v++) {
        if (!sptSet[v] && dist[v] < min) {
            min = dist[v];
            min_index = v;
        }
    }
    return min_index;
}

void dijkstra(int graph[V][V], int src) {
    int dist[V];
    bool sptSet[V];

    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        sptSet[i] = false;
    }

    dist[src] = 0;

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet); // pick closest unvisited
        sptSet[u] = true; // mark visited

        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v]; // update distance
            }
        }
    }

    printf("Vertex Distance from Source\n");
    for (int i = 0; i < V; i++) {
        printf("%c -> %d\n", 'S' + i, dist[i]);
    }
}

int main() {
    int graph[V][V] = {
        {0, 2, 5, 0},
        {0, 0, 1, 3},
        {0, 0, 0, 2},
        {0, 0, 0, 0}
    };

    dijkstra(graph, 0); // source is S (index 0)
    return 0;
}

int u = minDistance(dist, sptSet); // pick closest unvisited

select the unvisited node with the smallest current distance

sptSet[u] = true; // mark visited

mark this node as visited so we don't revisit

if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {

check if neighbor v can be reached with a shorter path through u

dist[v] = dist[u] + graph[u][v]; // update distance

update distance to neighbor v with shorter path found

Output

Vertex Distance from Source

S -> 0

A -> 2

B -> 3

C -> 5

Complexity Analysis

Time: O(V^2) because we check all vertices to find the minimum distance and update neighbors in nested loops

Space: O(V) for distance and visited arrays to store shortest path info

vs Alternative: Compared to using a priority queue (min-heap), this simple approach is slower (O(V^2) vs O(E log V)) but easier to understand and implement for small graphs

Edge Cases

Graph with no edges

Distances remain infinite except source which is zero

DSA C

dist[src] = 0;

Graph with single node

Distance to itself is zero, algorithm ends immediately

DSA C

for (int count = 0; count < V - 1; count++) {

Disconnected nodes

Distances to unreachable nodes remain infinite (INT_MAX)

DSA C

if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {

When to Use This Pattern

When you need shortest paths from one point to all others in a weighted graph without negative edges, reach for Dijkstra's algorithm because it efficiently finds minimum distances step-by-step.

Common Mistakes

Mistake: Not marking nodes as visited after selecting them
Fix: Set sptSet[u] = true immediately after picking the node with minimum distance

Mistake: Updating distances without checking if current distance is INT_MAX
Fix: Add condition dist[u] != INT_MAX before updating neighbors to avoid overflow

Summary

Finds shortest paths from a single source to all nodes in a weighted graph with non-negative edges.

Use when you want minimum travel cost or distance from one point to many points.

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

Practice

1. What is the main purpose of Dijkstra's Algorithm in graph theory?

easy

A. To sort the vertices of a graph topologically

B. To find the minimum spanning tree of a graph

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 goal of Dijkstra's Algorithm

   Dijkstra's Algorithm is designed to find the shortest distance 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

   Minimum spanning tree algorithms find a tree connecting all vertices with minimum total edge weight, cycle detection finds loops, and topological sort orders vertices in directed acyclic graphs. These are different goals.

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: Dijkstra finds shortest paths from one start point [OK]

Common Mistakes:

• Confusing with minimum spanning tree 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 C?

easy

A. int dist[V]; for(int i=0; i

B. int dist[V] = {INT_MAX};

C. int dist[V] = {0};

D. int dist[V] = NULL;

Solution

1. Step 1: Understand distance initialization

   Distances should start as infinity (or a very large number) except the source vertex, to represent unknown shortest paths.

2. Step 2: Check each option

   int dist[V] = {0}; initializes all distances to 0, which is incorrect. int dist[V]; for(int i=0; i

3. Final Answer:

   int dist[V]; for(int i=0; i -> Option A

4. Quick Check:

   Initialize distances to INT_MAX with loop [OK]

Hint: Use loop to set all distances to INT_MAX [OK]

Common Mistakes:

• Using {INT_MAX} initializes only first element
• Setting all distances to 0
• Assigning NULL to int array

3. What will be the output distances array after running Dijkstra's Algorithm from source vertex 0 on the following graph represented by adjacency matrix?

int graph[4][4] = {
  {0, 1, 4, 0},
  {1, 0, 2, 6},
  {4, 2, 0, 3},
  {0, 6, 3, 0}
};

medium

A. [0, 1, 4, 7]

B. [0, 1, 3, 5]

C. [0, 1, 3, 6]

D. [0, 2, 4, 6]

Solution

1. Step 1: Initialize distances and start from vertex 0

   Distances: dist[0]=0, dist[1]=∞, dist[2]=∞, dist[3]=∞. Update neighbors of 0: dist[1]=1, dist[2]=4.

2. Step 2: Pick vertex with smallest tentative distance and update neighbors

   Pick vertex 1 (dist=1). Update dist[2] = min(4, 1+2=3) = 3, dist[3] = min(∞, 1+6=7) = 7. Next pick vertex 2 (dist=3). Update dist[3] = min(7, 3+3=6) = 6. Finally pick vertex 3 (dist=6).

3. Final Answer:

   [0, 1, 3, 6] -> Option C

4. Quick Check:

   Distances after relaxation = [0,1,3,6] [OK]

Hint: Relax edges stepwise, pick smallest distance vertex next [OK]

Common Mistakes:

• Not updating distances after relaxation
• Choosing wrong next vertex
• Ignoring shorter paths through intermediate vertices

4. Identify the error in the following snippet of Dijkstra's Algorithm in C:

for (int count = 0; count < V-1; count++) {
  int u = minDistance(dist, sptSet);
  sptSet[u] = 1;
  for (int v = 0; v < V; v++) {
    if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
      dist[v] = dist[u] + graph[u][v];
    }
  }
}

medium

A. The loop should run from 1 to V instead of 0 to V-1

B. The condition 'graph[u][v]' should be 'graph[u][v] != 0' to check edge existence

C. The sptSet array should be initialized with 1 instead of 0

D. The dist[u] check should be 'dist[u] == INT_MAX' instead of '!='

Solution

1. Step 1: Analyze edge existence condition

   The condition 'graph[u][v]' relies on implicit truthiness of non-zero values. In C, this works but is less clear. Using 'graph[u][v] != 0' explicitly checks for edge presence and improves readability.

2. Step 2: Check other conditions

   Loop range from 0 to V-1 is correct for V vertices. sptSet should start with 0 (false). The dist[u] check must be '!= INT_MAX' to ensure u is reachable before relaxing edges.

3. Final Answer:

   The condition 'graph[u][v]' should be 'graph[u][v] != 0' to check edge existence -> Option B

4. Quick Check:

   Explicit edge check improves clarity [OK]

Hint: Use explicit '!= 0' to check edges in adjacency matrix [OK]

Common Mistakes:

• Assuming loop range is wrong
• Initializing sptSet incorrectly
• Reversing dist[u] check logic

5. Given a weighted graph with vertices 0 to 5 and edges:

0-1: 7, 0-2: 9, 0-5: 14, 1-2: 10, 1-3: 15, 2-3: 11, 2-5: 2, 3-4: 6, 4-5: 9

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

hard

A. 20

B. 26

C. 21

D. 19

Solution

1. Step 1: Initialize distances and start from vertex 0

   dist[0]=0, others = ∞. Update neighbors: dist[1]=7, dist[2]=9, dist[5]=14.

2. Step 2: Pick vertex with smallest dist and update neighbors

   Pick 1 (7): update dist[3] = min(∞, 7+15=22) = 22. Pick 2 (9): update dist[3] = min(22, 9+11=20) = 20, dist[5] = min(14, 9+2=11) = 11. Pick 5 (11): update dist[4] = min(∞, 11+9=20) = 20. Pick 3 (20): update dist[4] = min(20, 20+6=26) = 20. Pick 4 (20).

3. Final Answer:

   20 -> Option A

4. Quick Check:

   Shortest path to 4 = 20 [OK]

Hint: Relax edges carefully, update shortest distances stepwise [OK]

Common Mistakes:

• Not updating dist[5] to smaller value
• Ignoring shorter path through vertex 2
• Adding edges incorrectly