Weighted graphs in Data Structures Theory - Mini Project: Build & Apply

Understanding Weighted Graphs

📖 Scenario: You are learning about weighted graphs, which are used to represent networks where connections have values like distances or costs. Imagine a map of cities connected by roads, where each road has a length.

🎯 Goal: Build a simple weighted graph using a dictionary to represent cities and the distances between them. Then, add a threshold to find roads shorter than a certain distance.

📋 What You'll Learn

Create a dictionary called graph with exact city connections and weights

Add a variable called max_distance to set a distance limit

Use a for loop with variables city and connections to iterate over graph.items()

Inside the loop, use a nested for loop with variables neighbor and distance to iterate over connections.items()

Create a list called short_roads to store tuples of roads shorter than max_distance

💡 Why This Matters

🌍 Real World

Weighted graphs are used in maps, network routing, and scheduling to represent connections with costs or distances.

💼 Career

Understanding weighted graphs is important for roles in software development, data analysis, and network engineering.

1

Create the weighted graph dictionary

Create a dictionary called graph with these exact entries: 'A': {'B': 5, 'C': 10}, 'B': {'A': 5, 'C': 3}, 'C': {'A': 10, 'B': 3}

Data Structures Theory

# Create the weighted graph dictionary
# Your code here

Hint

Use a dictionary where each key is a city and each value is another dictionary of connected cities with distances.

2

Add a maximum distance threshold

Add a variable called max_distance and set it to 6 to represent the maximum road length to consider.

Data Structures Theory

graph = {
    'A': {'B': 5, 'C': 10},
    'B': {'A': 5, 'C': 3},
    'C': {'A': 10, 'B': 3}
}
# Add max_distance variable
# Your code here

Hint

This variable will help filter roads by length.

3

Find roads shorter than the threshold

Create an empty list called short_roads. Use a for loop with variables city and connections to iterate over graph.items(). Inside it, use another for loop with variables neighbor and distance to iterate over connections.items(). Append a tuple (city, neighbor, distance) to short_roads if distance is less than max_distance.

Data Structures Theory

graph = {
    'A': {'B': 5, 'C': 10},
    'B': {'A': 5, 'C': 3},
    'C': {'A': 10, 'B': 3}
}
max_distance = 6
# Create short_roads list and loop to find roads shorter than max_distance
# Your code here

Hint

Use nested loops to check each road's distance and add it to the list if it is less than max_distance.

4

Complete the weighted graph project

Add a final line that creates a variable called result and assigns it the value of short_roads to complete the project.

Data Structures Theory

graph = {
    'A': {'B': 5, 'C': 10},
    'B': {'A': 5, 'C': 3},
    'C': {'A': 10, 'B': 3}
}
max_distance = 6
short_roads = []
for city, connections in graph.items():
    for neighbor, distance in connections.items():
        if distance < max_distance:
            short_roads.append((city, neighbor, distance))
# Assign short_roads to result
# Your code here

Hint

This final step stores the filtered roads in a variable for further use.

Practice

1. What does the weight on an edge in a weighted graph usually represent?

easy

A. The cost or distance between two connected points

B. The color of the edge

C. The number of vertices in the graph

D. The direction of the edge

Solution

1. Step 1: Understand the role of weights in graphs

   Weights on edges represent values like cost, distance, or time between two connected points (vertices).

2. Step 2: Differentiate weights from other graph properties

   Weights are not about color, number of vertices, or direction but about measurable values on edges.

3. Final Answer:

   The cost or distance between two connected points -> Option A

4. Quick Check:

   Weight = cost/distance [OK]

Hint: Weights show cost or distance between points [OK]

Common Mistakes:

• Confusing weight with edge color
• Thinking weight counts vertices
• Mixing weight with edge direction

2. Which of the following is the correct way to represent a weighted edge between vertices A and B with weight 5?

easy

A. (A, B, 5)

B. {A: B = 5}

C. [A, B, weight=5]

D. A - B : 5

Solution

1. Step 1: Recognize common weighted edge notation

   Weighted edges are often represented as tuples like (vertex1, vertex2, weight).

2. Step 2: Check each option's format

   (A, B, 5) uses tuple format (A, B, 5), which is standard. Others are incorrect syntax or informal.

3. Final Answer:

   (A, B, 5) -> Option A

4. Quick Check:

   Weighted edge = (vertex1, vertex2, weight) [OK]

Hint: Use tuple (A, B, weight) for weighted edges [OK]

Common Mistakes:

• Using incorrect symbols like braces or colons
• Confusing syntax with dictionaries
• Writing weight as a keyword inside list

3. Consider the weighted graph edges: (A, B, 3), (B, C, 4), (A, C, 10). What is the shortest path weight from A to C?

medium

A. 4

B. 10

C. 3

D. 7

Solution

1. Step 1: Identify possible paths from A to C

   Paths: Direct (A to C) with weight 10, or via B: A to B (3) + B to C (4).

2. Step 2: Calculate total weights for each path

   Direct path weight = 10; via B = 3 + 4 = 7.

3. Final Answer:

   7 -> Option D

4. Quick Check:

   Shortest path weight = 7 [OK]

Hint: Sum weights on all paths, pick smallest [OK]

Common Mistakes:

• Choosing direct edge without checking alternatives
• Adding weights incorrectly
• Ignoring intermediate vertices

4. Given the weighted graph edges: (X, Y, 2), (Y, Z, 5), (X, Z, 4), a student claims the shortest path from X to Z is 7 by going through Y. What is wrong with this claim?

medium

A. They confused vertices Y and Z

B. They ignored the direct edge from X to Z with weight 4

C. They added weights incorrectly; 2 + 5 is not 7

D. They assumed edges are unweighted

Solution

1. Step 1: Analyze the paths from X to Z

   Paths: Direct edge (X, Z) with weight 4, and path via Y with weights 2 + 5 = 7.

2. Step 2: Identify the shortest path

   The direct edge weight 4 is less than 7, so shortest path is direct, not via Y.

3. Final Answer:

   They ignored the direct edge from X to Z with weight 4 -> Option B

4. Quick Check:

   Shortest path uses smallest weight edge [OK]

Hint: Check all edges before choosing path [OK]

Common Mistakes:

• Ignoring direct edges
• Incorrectly adding weights
• Mixing up vertex names

5. You have a weighted graph representing cities connected by roads with distances. To find the cheapest route from city A to city D considering toll costs on roads, which approach is best?

hard

A. Select the path with the most edges to maximize tolls

B. Count the number of roads between cities ignoring weights

C. Use a shortest path algorithm like Dijkstra's considering weights as toll costs

D. Use a depth-first search without considering weights

Solution

1. Step 1: Understand the problem context

   We want the cheapest route considering toll costs, which are weights on edges.

2. Step 2: Choose an appropriate algorithm

   Dijkstra's algorithm finds shortest paths in weighted graphs by minimizing total weight (cost).

3. Final Answer:

   Use a shortest path algorithm like Dijkstra's considering weights as toll costs -> Option C

4. Quick Check:

   Weighted shortest path = Dijkstra's algorithm [OK]

Hint: Use Dijkstra's for weighted shortest path problems [OK]

Common Mistakes:

• Ignoring weights and counting edges only
• Using DFS which ignores weights
• Choosing longest path mistakenly