Weighted graphs in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a weighted graph?

A weighted graph is a type of graph where each edge has a number called a weight. This weight often represents cost, distance, or time between two points.

beginner

How do weights in a graph help in real life?

Weights help show how much it costs or how far it is to move from one point to another, like distances on a map or prices in a network.

beginner

What is the difference between a weighted graph and an unweighted graph?

A weighted graph has numbers (weights) on edges, while an unweighted graph treats all edges as equal with no weights.

intermediate

What is a common use of weighted graphs in computer science?

Weighted graphs are used to find the shortest path between points, like GPS navigation or network routing.

advanced

Can weights in a weighted graph be negative? What does it mean?

Yes, weights can be negative in some cases. Negative weights might represent things like profit or gain, but they can make finding paths more complex.

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

A The cost or distance between two points

B The color of the edge

C The number of nodes in the graph

D The shape of the graph

Weights typically show cost, distance, or time between connected points.

Which of these is NOT true about weighted graphs?

A Edges have numbers called weights

B Weights can help find shortest paths

C Weights can represent time or cost

D All edges are considered equal

In weighted graphs, edges are not all equal because they have weights.

What is a common algorithm used with weighted graphs to find the shortest path?

A Dijkstra's algorithm

B Bubble sort

C Binary search

D Depth-first search

Dijkstra's algorithm is widely used to find shortest paths in weighted graphs.

Can weights in a weighted graph be negative?

A Only if the graph is unweighted

B Yes, sometimes

C No, never

D Only if the graph is directed

Weights can be negative in some graphs, but this requires special handling.

In a weighted graph, what does a higher weight on an edge usually mean?

A The edge is more important

B It is easier to travel

C It is more costly or longer to travel

D The edge connects more nodes

Higher weights usually mean higher cost or longer distance.

Explain what a weighted graph is and give a real-life example.

Think about how roads between cities have distances.

Describe why weights are important in graphs and how they affect finding paths.

Consider how GPS finds the fastest route.

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