Bellman Ford Algorithm Negative Weights 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 for initial distances is incorrect.

We use INT_MAX to represent infinity for initial distances.

2fill in blank

medium

Complete the code to relax edges inside the main loop.

DSA C

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

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

A0

Bweight

C-1

DINT_MAX

Attempts:

3 left

💡 Hint

Common Mistakes

Checking against 0 instead of INT_MAX causes wrong relaxations.

Not checking distance before relaxation leads to overflow.

We check if dist[u] is not infinity (INT_MAX) before relaxing.

3fill in blank

hard

Fix the error in the negative cycle detection condition.

DSA C

if (dist[u] != [1] && dist[u] + weight < dist[v]) {
    printf("Graph contains negative weight cycle\n");
    return 0;
}

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

AINT_MAX

B-1

C0

Dweight

Attempts:

3 left

💡 Hint

Common Mistakes

Checking against 0 or -1 causes incorrect negative cycle detection.

Not checking distance leads to runtime errors.

We must check dist[u] is not INT_MAX before detecting negative cycles.

4fill in blank

hard

Fill both blanks to complete the edge relaxation loop.

DSA C

for (int i = 1; i <= [1] - 1; i++) {
    for (int j = 0; j < [2]; j++) {
        int u = edges[j].src;
        int v = edges[j].dest;
        int weight = edges[j].weight;
        if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
            dist[v] = dist[u] + weight;
        }
    }
}

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

AV

BE

CV-1

DE-1

Attempts:

3 left

💡 Hint

Common Mistakes

Using V-1 instead of V for outer loop causes insufficient iterations.

Using E-1 for inner loop misses the last edge.

The outer loop runs V-1 times and the inner loop runs over all E edges.

5fill in blank

hard

Fill all three blanks to print the shortest distances after Bellman-Ford completes.

DSA C

printf("Vertex Distance from Source\n");
for (int i = 0; i < [1]; i++) {
    if (dist[i] == [2]) {
        printf("%d -> INF\n", [3]);
    } else {
        printf("%d -> %d\n", i, dist[i]);
    }
}

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

AV

BINT_MAX

Ci

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of INT_MAX causes wrong INF detection.

Printing wrong vertex index causes incorrect output.

Loop over all vertices V, check if distance is INT_MAX to print INF, and print vertex i.