Shortest Path in DAG Using Topological Order in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the distance array with infinity.

DSA C

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

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

AINT_MAX

B-1

C0

DNULL

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of a large number causes incorrect shortest path calculation.

Using NULL is invalid for integer arrays.

We use INT_MAX to represent infinity for initial distances.

2fill in blank

medium

Complete the code to perform topological sorting using DFS.

DSA C

void topologicalSortUtil(int v, int visited[], stack<int> &Stack) {
    visited[v] = 1;
    for (auto i : adj[v]) {
        if (!visited[i.first])
            [1](i.first, visited, Stack);
    }
    Stack.push(v);
}

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

Asort

BtopologicalSort

Cdfs

DtopologicalSortUtil

Attempts:

3 left

💡 Hint

Common Mistakes

Calling a non-existent function causes compilation errors.

Using the wrong function name breaks recursion.

The function calls itself recursively to visit all adjacent vertices.

3fill in blank

hard

Fix the error in updating the distance of adjacent vertices.

DSA C

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

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

Adist[v]

Bdist[u]

Cweight

DINT_MAX

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with dist[u] causes wrong updates.

Using weight alone ignores current distances.

We compare the new distance with the current distance of vertex v.

4fill in blank

hard

Fill both blanks to relax edges in topological order.

DSA C

while (!Stack.empty()) {
    int u = Stack.top();
    Stack.pop();

    if (dist[u] != INT_MAX) {
        for (auto i : adj[u]) {
            int v = i.first;
            int weight = i.second;
            if (dist[u] + [1] < dist[[2]]) {
                dist[v] = dist[u] + weight;
            }
        }
    }
}

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

Aweight

Bv

Cu

Ddist[u]

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up vertex names in comparison.

Using dist[u] instead of weight in addition.

We add the edge weight to dist[u] and compare with dist[v].

5fill in blank

hard

Fill all three blanks to print the shortest distances after processing.

DSA C

for (int i = 0; i < V; i++) {
    if (dist[i] == [1])
        printf("%d: INF\n", i);
    else
        printf("%d: %d\n", [2], [3]);
}

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

AINT_MAX

Bi

Cdist[i]

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Printing wrong variables causes incorrect output.

Not checking for infinity leads to wrong distance display.

We print INF if distance is INT_MAX, else print vertex and its distance.