Dijkstra's Algorithm Single Source Shortest Path in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the distance array with infinity.

DSA C

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

Drag options to blanks, or click blank then click option'

A1

B0

CINT_MAX

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of INT_MAX causes incorrect shortest path calculations.

Using negative values can cause logic errors.

We use INT_MAX to represent infinity for initial distances.

2fill in blank

medium

Complete the code to pick the vertex with the minimum distance value not yet processed.

DSA C

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

Drag options to blanks, or click blank then click option'

A<

B>

C==

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using > instead of < will select the maximum distance incorrectly.

Using == will not find the minimum properly.

We look for the vertex with the smallest distance value, so we use <.

3fill in blank

hard

Fix the error in the condition to update the distance of adjacent vertices.

DSA C

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

Drag options to blanks, or click blank then click option'

A>

B<

C==

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using > or >= will prevent updating shorter paths.

Using == will only update if distances are equal, which is incorrect.

We update the distance if the new path is shorter, so use <.

4fill in blank

hard

Fill both blanks to complete the loop that runs Dijkstra's algorithm for all vertices.

DSA C

for (int count = 0; count [1] V - 1; count++) {
    int u = [2](dist, sptSet);
    sptSet[u] = true;
    // Update dist values
}

Drag options to blanks, or click blank then click option'

A<

B<=

CminDistance

DmaxDistance

Attempts:

3 left

💡 Hint

Common Mistakes

Using <= causes one extra iteration.

Using maxDistance instead of minDistance picks wrong vertex.

The loop runs while count is less than V-1, and minDistance picks the next vertex.

5fill in blank

hard

Fill all three blanks to complete the code that prints the shortest distances from the source.

DSA C

void printSolution(int dist[], int n) {
    printf("Vertex \t Distance from Source\n");
    for (int [1] = 0; [1] < [2]; [1]++) {
        printf("%d \t\t %d\n", [3], dist[[1]]);
    }
}

Drag options to blanks, or click blank then click option'

Ai

Bn

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Using j instead of i in the loop variable causes confusion.

Looping until a wrong limit causes out-of-bounds errors.

Use i as the loop variable, loop until n, and print using i.

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