Dijkstra's algorithm in Data Structures Theory - Mini Project: Build & Apply

Dijkstra's Algorithm Step-by-Step

📖 Scenario: You are helping a delivery company find the shortest path between cities on a map. Each city is connected by roads with different distances. Your task is to use Dijkstra's algorithm to find the shortest distance from the starting city to all other cities.

🎯 Goal: Build a simple implementation of Dijkstra's algorithm that calculates the shortest distances from a starting city to all other cities in a given graph.

📋 What You'll Learn

Create a graph as a dictionary with cities as keys and their neighbors with distances as values

Set up a dictionary to hold the shortest distances initialized to infinity except the start city

Implement the core logic of Dijkstra's algorithm using a loop and updating distances

Complete the algorithm by returning the dictionary of shortest distances

💡 Why This Matters

🌍 Real World

Dijkstra's algorithm helps find the shortest routes in maps, GPS navigation, and network routing.

💼 Career

Understanding this algorithm is important for roles in software development, data science, and network engineering.

1

Create the graph data structure

Create a dictionary called graph representing the map with these exact entries: 'A': {'B': 5, 'C': 1}, 'B': {'A': 5, 'C': 2, 'D': 1}, 'C': {'A': 1, 'B': 2, 'D': 4, 'E': 8}, 'D': {'B': 1, 'C': 4, 'E': 3, 'F': 6}, 'E': {'C': 8, 'D': 3}, 'F': {'D': 6}

Data Structures Theory

# Create the graph dictionary with the exact city connections and distances
# Your code here

Need a hint?

Use a dictionary where each city points to another dictionary of neighbors and distances.

2

Initialize distances dictionary

Create a dictionary called distances with all cities from graph as keys and set their values to float('inf'). Then set the distance for the start city 'A' to 0.

Data Structures Theory

graph = {
    'A': {'B': 5, 'C': 1},
    'B': {'A': 5, 'C': 2, 'D': 1},
    'C': {'A': 1, 'B': 2, 'D': 4, 'E': 8},
    'D': {'B': 1, 'C': 4, 'E': 3, 'F': 6},
    'E': {'C': 8, 'D': 3},
    'F': {'D': 6}
}
# Create distances dictionary with all cities set to float('inf')
# Set distances['A'] to 0
# Your code here

Need a hint?

Use a dictionary comprehension to set all distances to infinity, then update the start city distance.

3

Implement the core Dijkstra's algorithm logic

Create a set called unvisited containing all cities from graph. Use a while loop that runs while unvisited is not empty. Inside the loop, find the city current_city in unvisited with the smallest distance in distances. Then, for each neighbor and distance in graph[current_city].items(), calculate a new distance and update distances[neighbor] if the new distance is smaller. Finally, remove current_city from unvisited.

Data Structures Theory

graph = {
    'A': {'B': 5, 'C': 1},
    'B': {'A': 5, 'C': 2, 'D': 1},
    'C': {'A': 1, 'B': 2, 'D': 4, 'E': 8},
    'D': {'B': 1, 'C': 4, 'E': 3, 'F': 6},
    'E': {'C': 8, 'D': 3},
    'F': {'D': 6}
}
distances = {city: float('inf') for city in graph}
distances['A'] = 0
# Create unvisited set with all cities
# Use while loop to process unvisited cities
# Find current_city with smallest distance
# Update distances for neighbors
# Remove current_city from unvisited
# Your code here

Need a hint?

Use min() with a key function to find the city with the smallest distance. Update neighbors only if the new distance is smaller.

4

Return the shortest distances

Add a final line to return the distances dictionary after the while loop ends.

Data Structures Theory

graph = {
    'A': {'B': 5, 'C': 1},
    'B': {'A': 5, 'C': 2, 'D': 1},
    'C': {'A': 1, 'B': 2, 'D': 4, 'E': 8},
    'D': {'B': 1, 'C': 4, 'E': 3, 'F': 6},
    'E': {'C': 8, 'D': 3},
    'F': {'D': 6}
}
distances = {city: float('inf') for city in graph}
distances['A'] = 0
unvisited = set(graph.keys())
while unvisited:
    current_city = min(unvisited, key=lambda city: distances[city])
    for neighbor, distance in graph[current_city].items():
        new_distance = distances[current_city] + distance
        if new_distance < distances[neighbor]:
            distances[neighbor] = new_distance
    unvisited.remove(current_city)
# Return the distances dictionary
# Your code here

Need a hint?

Simply add return distances after the loop to finish the algorithm.