Floyd-Warshall algorithm in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the distance matrix with the given graph weights.

Data Structures Theory

dist = [[[1] if i != j else 0 for j in range(n)] for i in range(n)]

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

Afloat('inf')

B0

C-1

DNone

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 for all distances, which incorrectly assumes all nodes are connected.

Using -1, which can cause confusion in comparisons.

The Floyd-Warshall algorithm starts by setting the distance between different nodes to infinity, indicating no direct path initially. The distance from a node to itself is zero.

2fill in blank

medium

Complete the code to update the distance matrix using an intermediate node k.

Data Structures Theory

if dist[i][k] != float('inf') and dist[k][j] != float('inf') and dist[i][j] > dist[i][k] [1] dist[k][j]:

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

A/

B-

C*

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction or multiplication instead of addition.

Not checking if intermediate paths are reachable.

The algorithm checks if going through node k offers a shorter path from i to j by adding the distances i to k and k to j.

3fill in blank

hard

Fix the error in the loop that iterates over all nodes as intermediate points.

Data Structures Theory

for [1] in range(n):

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

Ak

Bj

Ci

Dm

Attempts:

3 left

💡 Hint

Common Mistakes

Using i or j as the intermediate node variable, which conflicts with other loops.

Using an undefined variable like m.

The variable k is conventionally used to represent the intermediate node in Floyd-Warshall algorithm loops.

4fill in blank

hard

Fill both blanks to complete the nested loops iterating over all pairs of nodes.

Data Structures Theory

for [1] in range(n):
    for [2] in range(n):

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

Ai

Bj

Ck

Dm

Attempts:

3 left

💡 Hint

Common Mistakes

Using k or m in these loops, which are reserved for intermediate nodes or undefined.

Using the same variable for both loops.

The outer loop uses i for the start node and the inner loop uses j for the end node, covering all pairs.

5fill in blank

hard

Fill all three blanks to update the distance matrix inside the triple nested loops.

Data Structures Theory

if dist[[1]][[2]] > dist[[1]][[3]] + dist[[3]][[2]]:
    dist[[1]][[2]] = dist[[1]][[3]] + dist[[3]][[2]]

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

Ai

Bj

Ck

Dm

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up the order of indices.

Using undefined variables like m.

The indices i and j represent the start and end nodes, while k is the intermediate node used to check for shorter paths.