Shortest Path 2

Topics

Precalculus

Networks

Shortest Path

Shortest Path 2

Try VividMath Premium to unlock full access

Start Free Trial

Lets see your results!

Points

Score

Time

Retry Quiz

Answered
Review

Question 1 of 4

1. Question
Find the sequence of the shortest path from point $A$ $A$ to point $F$ $F$ .
- 1. $A - J - B - C - D - G - F$ $A-J-B-C-D-G-F$
- 2. $A - B - C - H - G - E - F$ $A-B-C-H-G-E-F$
- 3. $A - B - I - H - G - F$ $A-B-I-H-G-F$
- 4. $A - J - I - C - D - E - F$ $A-J-I-C-D-E-F$
Hint

Help Video
Correct

Excellent!
Incorrect
Need Text
Play
Current Time 0:00
/
Duration Time 0:00
Remaining Time -0:00
Stream TypeLIVE
Loaded: 0%
Progress: 0%
0:00
Fullscreen
Video Acceleration:
On
Off

00:00
Mute
Playback Rate
1x
2x
1.5x
1.25x
1x
0.75x
0.5x
Subtitles
subtitles off
Captions
captions off
English
Chapters
Chapters

Dijkstra’s Algorithm is a method of finding a shortest path from a vertex to another by comparing multiple paths and finding the shortest value or sum of values.

First, start finding the shortest paths to the vertices one edge away from $A$ $A$ , which are $B$ $B$ , and $J$ $J$ .

Always check for multiple paths and find the one with the lowest value.

$B$ $B$ $:$ $:$ $8$ $8$ or $5$ $5$

$J$ $J$ $:$ $:$ $2$ $2$

Now start finding the shortest paths to the vertices two edges away from $A$ $A$ , which are $C$ $C$ and $I$ $I$ .

Always check for multiple paths and find the one with the lowest value.

$C$ $C$ $:$ $:$ $6$ $6$

$I$ $I$ $:$ $:$ $8$ $8$ or $7$ $7$

Then start finding the shortest paths to the vertices three edges away from $A$ $A$ , which are $H$ $H$ and $D$ $D$ .

Always check for multiple paths and find the one with the lowest value.

$H$ $H$ $:$ $:$ $11$ $11$ or $8$ $8$

$D$ $D$ $:$ $:$ $12$ $12$ or $10$ $10$

Next, start finding the shortest paths to the vertices four edges away from $A$ $A$ , which are $G$ $G$ and $E$ $E$ .

Always check for multiple paths and find the one with the lowest value.

$G$ $G$ $:$ $:$ $16$ $16$ or $9$ $9$

$E$ $E$ $:$ $:$ $15$ $15$ or $11$ $11$

Now start finding the shortest paths to the vertex $F$ $F$ .

Always check for multiple paths and find the one with the lowest value.

$F$ $F$ $:$ $:$ $14$ $14$ or $12$ $12$

Finally, mark the shortest path from $A$ $A$ to $F$ $F$ to find its sequence.

Therefore, the sequence of the shortest path is $A - B - C - H - G - E - F$ $A-B-C-H-G-E-F$ .

$A - B - C - H - G - E - F$ $A-B-C-H-G-E-F$
Question 2 of 4

2. Question
The network shows the time table of a bus to travel to between bus stops. Find the sequence with the shortest time to travel from bus stop $Q$ $Q$ to $W$ $W$ .
- 1. $Q - R - S - T - V - W$ $Q-R-S-T-V-W$
- 2. $Q - X - Y - Z - W$ $Q-X-Y-Z-W$
- 3. $Q - U - V - W$ $Q-U-V-W$
- 4. $Q - U - V - T - W$ $Q-U-V-T-W$
Hint

Help Video
Correct

Nice Job!
Incorrect
Need Text
Play
Current Time 0:00
/
Duration Time 0:00
Remaining Time -0:00
Stream TypeLIVE
Loaded: 0%
Progress: 0%
0:00
Fullscreen
Video Acceleration:
On
Off

00:00
Mute
Playback Rate
1x
2x
1.5x
1.25x
1x
0.75x
0.5x
Subtitles
subtitles off
Captions
captions off
English
Chapters
Chapters

Dijkstra’s Algorithm is a method of finding a shortest path from a vertex to another by comparing multiple paths and finding the shortest value or sum of values.

First, start finding the shortest paths to the vertices one edge away from $Q$ $Q$ , which are $R$ $R$ , $U$ $U$ and $X$ $X$ .

Always check for multiple paths and find the one with the lowest value.

$R$ $R$ $:$ $:$ $25$ $25$ or $13$ $13$

$U$ $U$ $:$ $:$ $15$ $15$

$X$ $X$ $:$ $:$ $14$ $14$

Now start finding the shortest paths to the vertices two edges away from $Q$ $Q$ , which are $Y$ $Y$ , $S$ $S$ and $V$ $V$ .

Always check for multiple paths and find the one with the lowest value.

$Y$ $Y$ $:$ $:$ $23$ $23$

$S$ $S$ $:$ $:$ $27$ $27$ or $24$ $24$

$V$ $V$ $:$ $:$ $34, 30$ $34, 30$ or $28$ $28$

Then start finding the shortest paths to the vertices three edges away from $Q$ $Q$ , which are $T$ $T$ and $Z$ $Z$ .

Always check for multiple paths and find the one with the lowest value.

$T$ $T$ $:$ $:$ $39$ $39$ or $35$ $35$

$Z$ $Z$ $:$ $:$ $32$ $32$ or $29$ $29$

Now start finding the shortest paths to the vertex $W$ $W$ .

Always check for multiple paths and find the one with the lowest value.

$F$ $F$ $:$ $:$ $46, 45$ $46, 45$ or $44$ $44$

Finally, mark the shortest path from $Q$ $Q$ to $W$ $W$ to find its sequence.

Therefore, the sequence that will take the shortest time from $Q$ $Q$ to $W$ $W$ is $Q - U - V - T - W$ $Q-U-V-T-W$ .

$Q - U - V - T - W$ $Q-U-V-T-W$
Question 3 of 4

3. Question
Find the sequence of the shortest path from point $A$ $A$ to point $E$ $E$ .
- 1. $A - I - C - D - E$ $A-I-C-D-E$
- 2. $A - I - G - F - D - E$ $A-I-G-F-D-E$
- 3. $A - H - G - F - E$ $A-H-G-F-E$
- 4. $A - B - C - D - E$ $A-B-C-D-E$
Hint

Help Video
Correct

Well Done!
Incorrect
Need Text
Play
Current Time 0:00
/
Duration Time 0:00
Remaining Time -0:00
Stream TypeLIVE
Loaded: 0%
Progress: 0%
0:00
Fullscreen
Video Acceleration:
On
Off

00:00
Mute
Playback Rate
1x
2x
1.5x
1.25x
1x
0.75x
0.5x
Subtitles
subtitles off
Captions
captions off
English
Chapters
Chapters

Dijkstra’s Algorithm is a method of finding a shortest path from a vertex to another by comparing multiple paths and finding the shortest value or sum of values.

First, start finding the shortest paths to the vertices one edge away from $A$ $A$ , which are $B$ $B$ , $I$ $I$ and $H$ $H$ .

Always check for multiple paths and find the one with the lowest value.

$B$ $B$ $:$ $:$ $12$ $12$ or $11$ $11$

$I$ $I$ $:$ $:$ $5$ $5$

$H$ $H$ $:$ $:$ $7$ $7$

Now start finding the shortest paths to the vertices two edges away from $A$ $A$ , which are $G$ $G$ , $C$ $C$ and $J$ $J$ .

Always check for multiple paths and find the one with the lowest value.

$G$ $G$ $:$ $:$ $17$ $17$ or $12$ $12$

$C$ $C$ $:$ $:$ $22$ $22$ or $11$ $11$

$J$ $J$ $:$ $:$ $22, 21$ $22, 21$ or $14$ $14$

Then start finding the shortest paths to the vertices three edges away from $A$ $A$ , which are $F$ $F$ and $D$ $D$ .

Always check for multiple paths and find the one with the lowest value.

$F$ $F$ $:$ $:$ $26$ $26$ or $20$ $20$

$D$ $D$ $:$ $:$ $24$ $24$ or $22$ $22$

Now start finding the shortest paths to the vertex $E$ $E$ .

Always check for multiple paths and find the one with the lowest value.

$E$ $E$ $:$ $:$ $25$ $25$ or $24$ $24$

Finally, mark the shortest path from $A$ $A$ to $E$ $E$ to find its sequence.

Therefore, the sequence that will take the shortest path from $A$ $A$ to $E$ $E$ is $A - I - G - F - D - E$ $A-I-G-F-D-E$ .

$A - I - G - F - D - E$ $A-I-G-F-D-E$
Question 4 of 4

4. Question
The network shows the time in minutes for a car to travel to between points. Find the sequence with the shortest possible time to travel from $E$ $E$ to $J$ $J$ .
- 1. $E - L - P - K - J$ $E-L-P-K-J$
- 2. $E - L - K - J$ $E-L-K-J$
- 3. $E - M - N - O - Q - K - J$ $E-M-N-O-Q-K-J$
- 4. $E - F - G - H - Q - J$ $E-F-G-H-Q-J$
Hint

Help Video
Correct

Fantastic!
Incorrect
Need Text
Play
Current Time 0:00
/
Duration Time 0:00
Remaining Time -0:00
Stream TypeLIVE
Loaded: 0%
Progress: 0%
0:00
Fullscreen
Video Acceleration:
On
Off

00:00
Mute
Playback Rate
1x
2x
1.5x
1.25x
1x
0.75x
0.5x
Subtitles
subtitles off
Captions
captions off
English
Chapters
Chapters

Dijkstra’s Algorithm is a method of finding a shortest path from a vertex to another by comparing multiple paths and finding the shortest value or sum of values.

First, start finding the shortest paths to the vertices one edge away from $E$ $E$ , which are $F$ $F$ , $M$ $M$ and $L$ $L$ .

Always check for multiple paths and find the one with the lowest value.

$F$ $F$ $:$ $:$ $20$ $20$

$M$ $M$ $:$ $:$ $15$ $15$

$L$ $L$ $:$ $:$ $18$ $18$

Now start finding the shortest paths to the vertices two edges away from $E$ $E$ , which are $N$ $N$ , $G$ $G$ , $O$ $O$ and $P$ $P$ .

Always check for multiple paths and find the one with the lowest value.

$N$ $N$ $:$ $:$ $29$ $29$ or $22$ $22$

$G$ $G$ $:$ $:$ $36$ $36$ or $32$ $32$

$O$ $O$ $:$ $:$ $29$ $29$ or $25$ $25$

$P$ $P$ $:$ $:$ $32$ $32$ or $28$ $28$

Then start finding the shortest paths to the vertices three edges away from $E$ $E$ , which are $Q$ $Q$ , $K$ $K$ and $H$ $H$ .

Always check for multiple paths and find the one with the lowest value.

$Q$ $Q$ $:$ $:$ $29$ $29$

$K$ $K$ $:$ $:$ $39, 36$ $39, 36$ or $35$ $35$

$H$ $H$ $:$ $:$ $41$ $41$ or $37$ $37$

Now start finding the shortest paths to the vertices $J$ $J$ and $I$ $I$ .

Always check for multiple paths and find the one with the lowest value.

$J$ $J$ $:$ $:$ $41$ $41$ or $39$ $39$

$I$ $I$ $:$ $:$ $51$ $51$ or $44$ $44$

Finally, mark the shortest path from $E$ $E$ to $J$ $J$ to find its sequence.

Therefore, the sequence that will take the shortest time from $E$ $E$ to $J$ $J$ is $E - M - N - O - Q - K - J$ $E-M-N-O-Q-K-J$ .

$E - M - N - O - Q - K - J$ $E-M-N-O-Q-K-J$

Try VividMath Premium to unlock full access

Quiz summary

Information

1. Question

Hint

Excellent!

2. Question

Hint

Nice Job!

3. Question

Hint

Well Done!

4. Question

Hint

Fantastic!

Quizzes