9.3k views
2 votes
1. What length is the shortest path from A to C in the graph below?

A) 3
B) 4
C) 5 <
D) 9

2. What length is the shortest path from A to D in the graph below?
A) 6
B) 7
C) 8
D) 9

3. What length is the shortest path from A to G in the graph below?
A) 6
B) 7
C) 8
D) 9

1. What length is the shortest path from A to C in the graph below? A) 3 B) 4 C) 5 &lt-example-1
1. What length is the shortest path from A to C in the graph below? A) 3 B) 4 C) 5 &lt-example-1
1. What length is the shortest path from A to C in the graph below? A) 3 B) 4 C) 5 &lt-example-2
1. What length is the shortest path from A to C in the graph below? A) 3 B) 4 C) 5 &lt-example-3
User Marlowe
by
5.3k points

1 Answer

1 vote

Problem 1

Answer: C) 5

This is through point B. We have AB+BC = 2+3 = 5

Another path is AE+EB+BC = 4+1+3 = 8, which is longer than 5 found earlier.

Another path is AE+ED+DC = 4+3+2 = 9, which is longer as well.

Another path is AE+ED+DB+BC = 4+3+5+3 = 19, which is longer as well.

============================================

Problem 2

Answer: A) 6

This route is

AC+CF+FE+ED = 1+2+1+2 = 6

which is the shortest route

A longer route would be

AC+CF+FD = 1+2+4 = 7

Another longer route is

AB+BE+ED = 3+4+2 = 9

There are other longer routes as well.

============================================

Problem 3

Answer: B) 7

Start at point A. There are two paths to take. Take the shortest one AE = 1

Then from there repeat the last step: take the shortest path

Keep this up until you reach point G

AE+ED+DF+FG = 1+2+1+3 = 7

--------

Let's go back to point A. If we go to E, then we travel 1 unit so far. If we go for EH =8 instead of ED = 2, then we have 1+8 = 9 units traveled so far, but that exceeds 7 we found earlier. So we can rule this path out. This is one way you can use process of elimination to find the shortest path.

Similarly, go from A to B to C and we travel 2+5 = 7 units, which is equal to the answer, but we haven't reached G yet. So we can rule out any path that has ABC as the start.

The path ABDFG is not the shortest because AB+BD+DF+FG = 2+3+1+3 = 9, which is not shorter than 7.

User Laurence Burke
by
5.3k points