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.