Dijkstra's algorithm in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the distance to the start node as zero.

Data Structures Theory

distances = {node: float('inf') for node in graph}
distances[start] = [1]

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

A0

B1

Cfloat('inf')

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Setting the start node distance to infinity instead of zero.

Using a negative value for the start node distance.

In Dijkstra's algorithm, the distance to the start node is set to zero because it is the starting point.

2fill in blank

medium

Complete the code to select the unvisited node with the smallest distance.

Data Structures Theory

current_node = min(
    (node for node in unvisited),
    key=lambda node: distances[node]
) if unvisited else [1]

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

ANone

Bstart

C0

Dfloat('inf')

Attempts:

3 left

💡 Hint

Common Mistakes

Returning the start node again instead of None.

Returning a number like 0 or infinity which is not a node.

If there are no unvisited nodes left, the current node should be None to stop the algorithm.

3fill in blank

hard

Fix the error in updating the distance to a neighbor node.

Data Structures Theory

if distances[current_node] + graph[current_node][neighbor] < [1]:
    distances[neighbor] = distances[current_node] + graph[current_node][neighbor]

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

Agraph[neighbor][current_node]

Bdistances[neighbor]

Cdistances[current_node]

Ddistances[start]

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with the current node's distance instead of the neighbor's.

Using the start node's distance in the comparison.

The condition checks if the new calculated distance is less than the current known distance to the neighbor.

4fill in blank

hard

Fill in the blank to correctly update the previous node.

Data Structures Theory

if distances[current] + graph[current][neighbor] < distances[neighbor]:
    distances[neighbor] = distances[current] + graph[current][neighbor]
    previous[neighbor] = [1]

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

Astart

Bneighbor

Ccurrent

Ddistances

Attempts:

3 left

💡 Hint

Common Mistakes

Setting previous[neighbor] to neighbor.

Setting previous[neighbor] to start instead of current.

The previous node for the neighbor is set to the current node when a shorter path is found.

5fill in blank

hard

Fill all three blanks to build the shortest path from end to start.

Data Structures Theory

path = []
node = [1]
while node is not None:
    path.append(node)
    node = [2][node]
path = path[[3]]

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

Aend

Bprevious

C::-1

Ddistances

Attempts:

3 left

💡 Hint

Common Mistakes

Starting from the start node instead of the end.

Not reversing the path list at the end.

Start from the end node, follow previous nodes back to start, then reverse the path to get the correct order.