Bellman-Ford algorithm in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the distance to the source vertex as zero.

Data Structures Theory

distance[source] = [1]

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

Ainfinity

B-1

C0

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Setting the source distance to infinity or a negative number.

Forgetting to initialize the source distance.

The distance from the source vertex to itself is always zero in the Bellman-Ford algorithm.

2fill in blank

medium

Complete the code to relax an edge from u to v with weight w.

Data Structures Theory

if distance[u] != [1] and distance[u] + w < distance[v]:

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

A0

Binfinity

C-1

DNone

Attempts:

3 left

💡 Hint

Common Mistakes

Checking if distance[u] is zero instead of infinity.

Not checking if u is reachable before relaxing.

We check if the distance to u is not infinity before relaxing the edge, to ensure u is reachable.

3fill in blank

hard

Fix the error in the loop that runs the relaxation steps for all vertices.

Data Structures Theory

for i in range([1] - 1):

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

Alen(graph)

Blen(graph) + 1

Clen(graph) * 2

Dlen(graph) - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using the number of edges instead of vertices.

Using the full number of vertices instead of one less.

The Bellman-Ford algorithm requires |V| - 1 iterations to relax all edges, where |V| is the number of vertices.

4fill in blank

hard

Fill both blanks to check for negative weight cycles after relaxation.

Data Structures Theory

for u, v, w in edges:
    if distance[u] != [1] and distance[u] + w < [2]:

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

Ainfinity

Bdistance[v]

C0

Ddistance[u]

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with distance[u] instead of distance[v].

Not checking if distance[u] is reachable.

After all relaxations, if we can still relax an edge, it means a negative weight cycle exists.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension for distances after relaxation.

Data Structures Theory

distances = {vertex: [1] for vertex in graph if graph[vertex] [2] [3]

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

A0

B!=

CNone

Dinfinity

Attempts:

3 left

💡 Hint

Common Mistakes

Using '==' instead of '!=' in the condition.

Setting distance to infinity instead of zero.

This comprehension sets distance 0 for vertices that are reachable (not None).