Dijkstra's Algorithm Single Source Shortest Path in DSA Python - Build from Scratch

Dijkstra's Algorithm Single Source Shortest Path

📖 Scenario: Imagine you are a delivery driver who needs to find the shortest path from your warehouse to all the stores in a city. The city map is represented as a network of roads connecting different locations with distances.

🎯 Goal: You will build a program that uses Dijkstra's algorithm to find the shortest distance from the warehouse (starting point) to every other location on the map.

📋 What You'll Learn

Create a graph as a dictionary where keys are node names and values are dictionaries of neighbors with distances

Set a starting node for the algorithm

Implement Dijkstra's algorithm to find shortest paths

Print the shortest distances from the start node to all other nodes

💡 Why This Matters

🌍 Real World

Delivery services, GPS navigation, and network routing use shortest path algorithms like Dijkstra's to find the quickest routes.

💼 Career

Understanding Dijkstra's algorithm is important for software engineers working in logistics, mapping, telecommunications, and any field involving graph data.

1

Create the city map graph

Create a dictionary called graph representing the city map with these exact nodes and edges: 'A' connects to 'B' with distance 5 and 'C' with distance 1; 'B' connects to 'A' with distance 5 and 'C' with distance 2 and 'D' with distance 1; 'C' connects to 'A' with distance 1 and 'B' with distance 2 and 'D' with distance 4 and 'E' with distance 8; 'D' connects to 'B' with distance 1 and 'C' with distance 4 and 'E' with distance 3; 'E' connects to 'C' with distance 8 and 'D' with distance 3.

DSA Python

# Create the graph dictionary with nodes and edges
# Your code here

Hint

Use a dictionary where each key is a node and its value is another dictionary of neighbors with distances.

2

Set the starting node

Create a variable called start_node and set it to the string 'A' to represent the warehouse starting point.

DSA Python

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},
    'E': {'C': 8, 'D': 3}
}
# Set the start_node to 'A'
# Your code here

Hint

Just assign the string 'A' to the variable start_node.

3

Implement Dijkstra's algorithm

Write code to implement Dijkstra's algorithm using the graph and start_node. Create a dictionary called distances to store shortest distances initialized with infinity for all nodes except start_node which should be 0. Use a set called unvisited containing all nodes. While unvisited is not empty, pick the node with the smallest distance, update distances for its neighbors if shorter paths are found, and remove the node from unvisited.

DSA Python

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},
    'E': {'C': 8, 'D': 3}
}

start_node = 'A'

# Implement Dijkstra's algorithm below
# Your code here

Hint

Use a dictionary comprehension to set initial distances. Use a while loop to process nodes. Use min() with a key function to find the closest unvisited node.

4

Print the shortest distances

Write a for loop to print the shortest distances from start_node to each node in distances in the format: Node A: 0, Node B: 3, etc.

DSA Python

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},
    'E': {'C': 8, 'D': 3}
}

start_node = 'A'

# Initialize distances with infinity
distances = {node: float('inf') for node in graph}
distances[start_node] = 0

# Set of unvisited nodes
unvisited = set(graph.keys())

while unvisited:
    # Pick the unvisited node with the smallest distance
    current_node = min(
        (node for node in unvisited),
        key=lambda node: distances[node]
    )

    # Update distances to neighbors
    for neighbor, distance in graph[current_node].items():
        if neighbor in unvisited:
            new_distance = distances[current_node] + distance
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance

    # Mark current node as visited
    unvisited.remove(current_node)

# Print shortest distances
# Your code here

Hint

Use a for loop to go through each node in distances and print the node and its distance using an f-string.

Practice

1. What is the main purpose of Dijkstra's Algorithm in graph theory?

easy

A. To sort vertices in topological order

B. To find the maximum flow in a network

C. To detect cycles in a graph

D. To find the shortest path from a single source to all other vertices

Solution

1. Step 1: Understand the algorithm's goal

   Dijkstra's Algorithm is designed to find the shortest distance from one starting point (source) to every other point in a graph.

2. Step 2: Compare with other graph algorithms

   Other algorithms like max flow or cycle detection serve different purposes, so they do not match Dijkstra's goal.

3. Final Answer:

   To find the shortest path from a single source to all other vertices -> Option D

4. Quick Check:

   Shortest path = find minimum distances [OK]

Hint: Dijkstra finds shortest paths from one start point [OK]

Common Mistakes:

• Confusing with max flow algorithms
• Thinking it detects cycles
• Assuming it sorts vertices

2. Which Python data structure is commonly used to efficiently select the next vertex with the smallest tentative distance in Dijkstra's Algorithm?

easy

A. List

B. Heap (Priority Queue)

C. Queue

D. Set

Solution

1. Step 1: Identify the need for efficient minimum extraction

   Dijkstra's Algorithm repeatedly picks the vertex with the smallest tentative distance, so an efficient way to get the minimum is needed.

2. Step 2: Choose the right data structure

   A heap or priority queue allows quick extraction of the smallest element, unlike lists or queues which are slower for this task.

3. Final Answer:

   Heap (Priority Queue) -> Option B

4. Quick Check:

   Priority queue = efficient min extraction [OK]

Hint: Use a heap to get smallest distance vertex fast [OK]

Common Mistakes:

• Using a simple list which is slow
• Using a queue which is FIFO, not min-based
• Using a set which has no order

3. What will be the output distances array after running Dijkstra's Algorithm from source vertex 0 on this graph represented by adjacency list with weights?

graph = {
  0: [(1, 4), (2, 1)],
  1: [(3, 1)],
  2: [(1, 2), (3, 5)],
  3: []
}

medium

A. [0, 4, 1, 6]

B. [0, 2, 1, 3]

C. [0, 3, 1, 4]

D. [0, 1, 2, 5]

Solution

1. Step 1: Initialize distances and start from vertex 0

   Distances: 0 to 0 = 0, others infinity initially. Update neighbors: vertex 1 = 4, vertex 2 = 1.

2. Step 2: Pick vertex with smallest distance (2), update neighbors

   From vertex 2, update vertex 1: min(4, 1+2=3) = 3, vertex 3 = 1+5=6.

3. Step 3: Pick vertex with smallest distance (1), update neighbors

   From vertex 1, update vertex 3: min(6, 3+1=4) = 4.

4. Step 4: Final distances

   Distances array is [0, 3, 1, 4].

5. Final Answer:

   [0, 3, 1, 4] -> Option C

6. Quick Check:

   Distances updated stepwise = [0, 3, 1, 4] [OK]

Hint: Update neighbors with min distance each step [OK]

Common Mistakes:

• Not updating vertex 1 distance from vertex 2
• Ignoring better path to vertex 3
• Mixing up edge weights

4. Consider this Dijkstra's Algorithm snippet in Python:

def dijkstra(graph, source):
    dist = {v: float('inf') for v in graph}
    dist[source] = 0
    visited = set()
    while len(visited) < len(graph):
        u = min((v for v in graph if v not in visited), key=lambda x: dist[x])
        visited.add(u)
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist

What is the main issue with it?

medium

A. The algorithm does not use a priority queue for efficiency

B. The visited set is not updated properly

C. The algorithm does not handle unreachable vertices

D. The algorithm does not update distances correctly

Solution

1. Step 1: Analyze the selection of next vertex

   The code uses min() over all unvisited vertices to find the smallest distance vertex, which is correct but inefficient.

2. Step 2: Identify efficiency problem

   Without a priority queue, each min() call takes O(V) time, making the algorithm slower but still correct logically.

3. Step 3: Check for correctness vs efficiency

   Though inefficient, the code updates distances and visited set correctly, so the main issue is lack of priority queue for efficiency.

4. Final Answer:

   The algorithm does not use a priority queue for efficiency -> Option A

5. Quick Check:

   Missing priority queue = inefficient but correct [OK]

Hint: Dijkstra needs priority queue for speed, else slow [OK]

Common Mistakes:

• Thinking visited set is not updated
• Assuming distance updates are wrong
• Confusing unreachable vertex handling

5. Given a weighted graph with negative edge weights but no negative cycles, why can't Dijkstra's Algorithm be used to find shortest paths from a source vertex?

hard

A. Because Dijkstra's Algorithm assumes all edge weights are non-negative

B. Because Dijkstra's Algorithm cannot handle graphs with cycles

C. Because Dijkstra's Algorithm requires the graph to be directed acyclic

D. Because Dijkstra's Algorithm only works on unweighted graphs

Solution

1. Step 1: Understand Dijkstra's assumption on edge weights

   Dijkstra's Algorithm assumes all edge weights are zero or positive to guarantee correctness.

2. Step 2: Explain why negative weights break the algorithm

   Negative weights can cause the algorithm to miss shorter paths found later, as it greedily picks the smallest tentative distance.

3. Step 3: Clarify other options

   The algorithm can handle cycles if no negative cycles exist, and it works on weighted graphs, not just unweighted.

4. Final Answer:

   Because Dijkstra's Algorithm assumes all edge weights are non-negative -> Option A

5. Quick Check:

   Negative weights break Dijkstra's assumptions [OK]

Hint: Dijkstra fails if any edge weight is negative [OK]

Common Mistakes:

• Thinking it can't handle cycles at all
• Believing it only works on unweighted graphs
• Confusing negative cycles with negative edges