Weighted graphs in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding weighted graph edges

In a weighted graph, what does the weight on an edge represent?

A The total number of edges in the graph

B The number of nodes connected by the edge

C The color assigned to the edge for visualization

D A value representing the cost, distance, or capacity between two nodes

💡 Hint

Think about what extra information a weighted graph provides compared to an unweighted graph.

The weight on an edge in a weighted graph usually represents a measurable value like cost, distance, or capacity between the two connected nodes.

📋 Factual

intermediate

Weighted graph representation

Which data structure is commonly used to represent a weighted graph efficiently?

A Adjacency matrix with weights stored in cells

B Simple list of nodes without edges

C Stack storing nodes in order of visitation

D Queue storing nodes for breadth-first traversal

💡 Hint

Consider how to store both connections and their weights compactly.

An adjacency matrix stores weights directly in the cells representing edges between nodes, making it a common choice for weighted graphs.

🔍 Analysis

advanced

Shortest path in weighted graphs

Given a weighted graph with positive edge weights, which algorithm is best suited to find the shortest path from one node to all others?

A Dijkstra's algorithm

B Topological sort

C Breadth-first search (BFS)

D Depth-first search (DFS)

💡 Hint

Think about an algorithm that considers edge weights and finds minimum distances efficiently.

Dijkstra's algorithm is designed to find the shortest path in weighted graphs with non-negative weights by exploring nodes with the smallest tentative distance first.

❓ Comparison

advanced

Difference between weighted and unweighted graphs

Which statement correctly distinguishes a weighted graph from an unweighted graph?

A Unweighted graphs cannot have cycles; weighted graphs can.

B Weighted graphs have edges with values representing costs; unweighted graphs treat all edges equally.

C Weighted graphs always have directed edges; unweighted graphs have undirected edges.

D Weighted graphs have more nodes than unweighted graphs.

💡 Hint

Focus on what extra information weighted graphs carry on edges.

Weighted graphs assign values to edges to represent costs or distances, while unweighted graphs consider all edges equal without weights.

❓ Reasoning

expert

Impact of negative weights in weighted graphs

What issue arises when using Dijkstra's algorithm on a weighted graph that contains negative edge weights?

A The algorithm will run faster because negative weights reduce distances.

B Dijkstra's algorithm will ignore negative edges and only consider positive ones.

C Dijkstra's algorithm may produce incorrect shortest path results because it assumes all weights are non-negative.

D There is no issue; Dijkstra's algorithm works correctly with negative weights.

💡 Hint

Consider the assumptions Dijkstra's algorithm makes about edge weights.

Dijkstra's algorithm assumes all edge weights are non-negative. Negative weights can cause it to miss shorter paths, leading to incorrect results.

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