Shortest Path 1

Topics

Precalculus

Networks

Shortest Path

Shortest Path 1

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 shortest path from $A$ $A$ to all other points.
- $From$ $\text(From)$ $A$ $A$
  
  $To$ $\text(To)$ $B$ $B$ (7)
  
  $C$ $C$ (13)
  
  $D$ $D$ (15)
  
  $E$ $E$ (8)
  
  $F$ $F$ (1)
  
  $G$ $G$ (5)
  
  $H$ $H$ (9)
Hint

Help Video
Correct

Great Work!
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, mark the starting vertex, which is $A$ $A$ .

Next, start finding the shortest paths to the closest vertices, which are $B$ $B$ , $G$ $G$ , and $F$ $F$ .

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

$F$ $F$ $:$ $:$ $1$ $1$

$G$ $G$ $:$ $:$ $5$ $5$

$B$ $B$ $:$ $:$ $8$ $8$ or $7$ $7$

Now start finding the shortest paths to the remaining vertices, which are $E$ $E$ , $H$ $H$ , $C$ $C$ and $D$ $D$ .

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

$E$ $E$ $:$ $:$ $11$ $11$ or $8$ $8$

$H$ $H$ $:$ $:$ $13, 10$ $13, 10$ or $9$ $9$

$C$ $C$ $:$ $:$ $16$ $16$ or $13$ $13$

$D$ $D$ $:$ $:$ $21$ $21$ or $15$ $15$

Finally, fill in the table with the values of the shortest paths.

$From$ $\text(From)$ $A$ $A$

$To$ $\text(To)$ $B$ $B$ $7$ $7$

$C$ $C$ $13$ $13$

$D$ $D$ $15$ $15$

$E$ $E$ $8$ $8$

$F$ $F$ $1$ $1$

$G$ $G$ $5$ $5$

$H$ $H$ $9$ $9$
Question 2 of 4

2. Question
The diagram shows the biking track around a park reserve. The values are the kilometres to be traveled to reach each point. Find the shortest path from point $P$ $P$ to all the other points.
- $From$ $\text(From)$ $P$ $P$
  
  $To$ $\text(To)$ $Q$ $Q$ (3)
  
  $R$ $R$ (5)
  
  $S$ $S$ (7)
  
  $T$ $T$ (8)
  
  $U$ $U$ (6)
  
  $V$ $V$ (2)
  
  $W$ $W$ (1)
  
  $X$ $X$ (4)
  
  $Y$ $Y$ (6)
Hint

Help Video
Correct

Correct!
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, mark the starting vertex, which is $P$ $P$ .

Next, start finding the shortest paths to the closest vertices, which are $Q$ $Q$ , $W$ $W$ , and $V$ $V$ .

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

$Q$ $Q$ $:$ $:$ $4$ $4$ or $3$ $3$

$W$ $W$ $:$ $:$ $1$ $1$

$V$ $V$ $:$ $:$ $3$ $3$ or $2$ $2$

Now start finding the shortest paths to the vertices two edges away from $P$ $P$ , which are $R$ $R$ , and $X$ $X$ .

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

$R$ $R$ $:$ $:$ $6$ $6$ or $5$ $5$

$X$ $X$ $:$ $:$ $4$ $4$

Now start finding the shortest paths to the remaining vertices, which are $Y$ $Y$ , $S$ $S$ , $T$ $T$ , and $U$ $U$ .

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

$Y$ $Y$ $:$ $:$ $7$ $7$ or $6$ $6$

$S$ $S$ $:$ $:$ $7$ $7$

$T$ $T$ $:$ $:$ $10$ $10$ or $8$ $8$

$U$ $U$ $:$ $:$ $7$ $7$ or $6$ $6$

Finally, fill in the table with the values of the shortest paths.

$From$ $\text(From)$ $P$ $P$

$To$ $\text(To)$ $Q$ $Q$ $3$ $3$

$R$ $R$ $5$ $5$

$S$ $S$ $7$ $7$

$T$ $T$ $8$ $8$

$U$ $U$ $6$ $6$

$V$ $V$ $2$ $2$

$W$ $W$ $1$ $1$

$X$ $X$ $4$ $4$

$Y$ $Y$ $6$ $6$
Question 3 of 4

3. Question
The network show the value in thousand dollars for putting up fiber optic cables to each location. Find the cost of putting up a cable from $A$ $A$ to $D$ $D$
- $$$ $$$ (29000)
Hint

Help Video
Correct

Keep Going!
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 $F$ $F$ , $E$ $E$ , and $B$ $B$ .

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

$F$ $F$ $:$ $:$ $16$ $16$ or $12$ $12$

$E$ $E$ $:$ $:$ $17$ $17$ or $16$ $16$

$B$ $B$ $:$ $:$ $15, 16$ $15, 16$ or $10$ $10$

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

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

$G$ $G$ $:$ $:$ $26, 26, 27$ $26, 26, 27$ or $24$ $24$

$C$ $C$ $:$ $:$ $29$ $29$ or $24$ $24$

Now start finding the paths to vertex $D$ $D$ .

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

$D$ $D$ $:$ $:$ $33, 32$ $33, 32$ or $29$ $29$

Take note that each value in the network represents a thousand dollars.

Therefore, a connection from $A$ $A$ to $D$ $D$ will cost $$ 29000$ $$29000$ .

$$ 29000$ $$29000$
Question 4 of 4

4. Question
The network shows the flights around New South Wales with the cost listed in dollars. What is the cheapest rate to fly from Sydney to Dubbo?
- $$$ $$$ (600)
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.

Try out multiple paths that will travel from Sydney to Dubbo and find the one with the least cost.

$Sydney-Woollongong-Wagga Wagga-Dubbo$ $\text(Sydney-Woollongong-Wagga Wagga-Dubbo)$ $:$ $:$ $$ 610$ $$610$

$Sydney-Bathurst-Dubbo$ $\text(Sydney-Bathurst-Dubbo)$ $:$ $:$ $$ 610$ $$610$

$Sydney-Dubbo$ $\text(Sydney-Dubbo)$ $:$ $:$ $$ 610$ $$610$

$Sydney-Tamworth-Dubbo$ $\text(Sydney-Tamworth-Dubbo)$ $:$ $:$ $$ 630$ $$630$

$Sydney-Coffs Harbour-Tamworth-Dubbo$ $\text(Sydney-Coffs Harbour-Tamworth-Dubbo)$ $:$ $:$ $$ 600$ $$600$

Therefore, the cheapest flight to take to get from Sydney to Dubbo will cost $$ 600$ $$600$ .

$$ 600$ $$600$