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 AA.
Next, start finding the shortest paths to the closest vertices, which are BB, GG, and FF.
Always check for multiple paths and find the one with the lowest value.
FF
::
11
GG
::
55
BB
::
88 or 77
Now start finding the shortest paths to the remaining vertices, which are EE, HH, CC and DD.
Always check for multiple paths and find the one with the lowest value.
EE
::
1111 or 88
HH
::
13,1013,10 or 99
CC
::
1616 or 1313
DD
::
2121 or 1515
Finally, fill in the table with the values of the shortest paths.
FromFrom
AA
ToTo
BB
77
CC
1313
DD
1515
EE
88
FF
11
GG
55
HH
99
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 PP to all the other points.
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 PP.
Next, start finding the shortest paths to the closest vertices, which are QQ, WW, and VV.
Always check for multiple paths and find the one with the lowest value.
QQ
::
44 or 33
WW
::
11
VV
::
33 or 22
Now start finding the shortest paths to the vertices two edges away from PP, which are RR, and XX.
Always check for multiple paths and find the one with the lowest value.
RR
::
66 or 55
XX
::
44
Now start finding the shortest paths to the remaining vertices, which are YY, SS, TT, and UU.
Always check for multiple paths and find the one with the lowest value.
YY
::
77 or 66
SS
::
77
TT
::
1010 or 88
UU
::
77 or 6
Finally, fill in the table with the values of the shortest paths.
From
P
To
Q
3
R
5
S
7
T
8
U
6
V
2
W
1
X
4
Y
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 to D
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, which are F, E, and B.
Always check for multiple paths and find the one with the lowest value.
F
:
16 or 12
E
:
17 or 16
B
:
15,16 or 10
Now start finding the shortest paths to the vertices two edges away from A, which are G and C.
Always check for multiple paths and find the one with the lowest value.
G
:
26,26,27 or 24
C
:
29 or 24
Now start finding the paths to vertex D.
Always check for multiple paths and find the one with the lowest value.
D
:
33,32 or 29
Take note that each value in the network represents a thousand dollars.
Therefore, a connection from A to D will cost $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?
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
:
$610
Sydney-Bathurst-Dubbo
:
$610
Sydney-Dubbo
:
$610
Sydney-Tamworth-Dubbo
:
$630
Sydney-Coffs Harbour-Tamworth-Dubbo
:
$600
Therefore, the cheapest flight to take to get from Sydney to Dubbo will cost $600.