Dijkstra's Algorithm

Error

There was an error loading the page.

Contributors

Stephen Maher

Feedback

From users who are members of Stephen's workspace :

Stephen Maher

said

Ready to use

3 years, 4 months ago

History

○

Stephen Maher 3 years, 4 months ago

Gave some feedback: Ready to use

○

Stephen Maher 3 years, 4 months ago

Published this.

○

Stephen Maher 3 years, 4 months ago

Created this.

There is only one version of this question that you have access to.

There is one other version that you do not have access to.

Question statement

Consider the undirected graph

with the edge weights

	a	b	c	d	e	f	g	h
a		{ab}	{ac}	{ad}
b	{ab}		{bc}			{bf}
c	{ac}	{bc}			{ce}			{ch}
d	{ad}				{de}	{df}
e			{ce}	{de}			{eg}	{eh}
f		{bf}		{df}			{fg}
g					{eg}	{fg}		{gh}
h			{ch}		{eh}		{gh}

Give any introductory information the student needs.

			Name	Type	Generated Value

ab	integer	3
ac	integer	1
ad	integer	4
ae	integer	2
bc	integer	4
bf	integer	1
ce	integer	5
cg	integer	5
de	integer	4
df	integer	3
dg	integer	5
eg	integer	1
fg	integer	3
sinkoptions	list	[ "f", "g", "h" ]
sinkchoice	integer	2
sink	string	h
edgeweights	list	Nested 8×8 list
shortestdist	list	[ 4, 7, 5 ]
distances	list	Nested 8×8×2 list
answer	number	5
nodenames	list	List of 8 items
numnodes	number	8
ch	integer	4
eh	integer	1
gh	integer	5
maxweight	integer	5

Automatically regenerate variables?

Name

Data type

Value

xxxxxxxxxx
 
random(1..maxweight)

JME function reference

Description

Describe what this variable represents, and list any assumptions made about its value.

Can an exam override the value of this variable?

Generated value: `integer`

← Depends on:

This variable doesn't seem to be used anywhere.

Advice

Since this graph is small, it is possible to determine the shortest path by inspection. However, it is a good test to use Dijkstra's algorithm to find the shortest path.

The shortest path length is given by the sum of the edges from the source node, which is (a), to the sink node, which is ({sink}).

Below is a step through of Dijkstra's algorithm. The entry in each cell is (predecessor, distance), where predecessor is the node immediately before this node in the shortest path and the distance is the distance to that node in the shortest path. If the entry in a row is (-, -), then the algorithm has not yet added the vertex to the shortest path tree.

Step	a	b	c	d	e	f	g	h
1	(s,0)	({if(distances[0][1][1]=9999,"-", nodenames[distances[0][1][0]])}, {if(distances[0][1][1]=9999,"-", distances[0][1][1])})	({if(distances[0][2][1]=9999,"-", nodenames[distances[0][2][0]])}, {if(distances[0][2][1]=9999,"-", distances[0][2][1])})	({if(distances[0][3][1]=9999,"-", nodenames[distances[0][3][0]])}, {if(distances[0][3][1]=9999,"-", distances[0][3][1])})	({if(distances[0][4][1]=9999,"-", nodenames[distances[0][4][0]])}, {if(distances[0][4][1]=9999,"-", distances[0][4][1])})	({if(distances[0][5][1]=9999,"-", nodenames[distances[0][5][0]])}, {if(distances[0][5][1]=9999,"-", distances[0][5][1])})	({if(distances[0][6][1]=9999,"-", nodenames[distances[0][6][0]])}, {if(distances[0][6][1]=9999,"-", distances[1][6][1])})	({if(distances[0][7][1]=9999,"-", nodenames[distances[0][7][0]])}, {if(distances[0][7][1]=9999,"-", distances[1][7][1])})
2	(s,0)	({if(distances[1][1][1]=9999,"-", nodenames[distances[1][1][0]])}, {if(distances[1][1][1]=9999,"-", distances[1][1][1])})	({if(distances[1][2][1]=9999,"-", nodenames[distances[1][2][0]])}, {if(distances[1][2][1]=9999,"-", distances[1][2][1])})	({if(distances[1][3][1]=9999,"-", nodenames[distances[1][3][0]])}, {if(distances[1][3][1]=9999,"-", distances[1][3][1])})	({if(distances[1][4][1]=9999,"-", nodenames[distances[1][4][0]])}, {if(distances[1][4][1]=9999,"-", distances[1][4][1])})	({if(distances[1][5][1]=9999,"-", nodenames[distances[1][5][0]])}, {if(distances[1][5][1]=9999,"-", distances[1][5][1])})	({if(distances[1][6][1]=9999,"-", nodenames[distances[1][6][0]])}, {if(distances[1][6][1]=9999,"-", distances[1][6][1])})	({if(distances[1][7][1]=9999,"-", nodenames[distances[1][7][0]])}, {if(distances[1][7][1]=9999,"-", distances[1][7][1])})
3	(s,0)	({if(distances[2][1][1]=9999,"-", nodenames[distances[2][1][0]])}, {if(distances[2][1][1]=9999,"-", distances[2][1][1])})	({if(distances[2][2][1]=9999,"-", nodenames[distances[2][2][0]])}, {if(distances[2][2][1]=9999,"-", distances[2][2][1])})	({if(distances[2][3][1]=9999,"-", nodenames[distances[2][3][0]])}, {if(distances[2][3][1]=9999,"-", distances[2][3][1])})	({if(distances[2][4][1]=9999,"-", nodenames[distances[2][4][0]])}, {if(distances[2][4][1]=9999,"-", distances[2][4][1])})	({if(distances[2][5][1]=9999,"-", nodenames[distances[2][5][0]])}, {if(distances[2][5][1]=9999,"-", distances[2][5][1])})	({if(distances[2][6][1]=9999,"-", nodenames[distances[2][6][0]])}, {if(distances[2][6][1]=9999,"-", distances[2][6][1])})	({if(distances[2][7][1]=9999,"-", nodenames[distances[2][7][0]])}, {if(distances[2][7][1]=9999,"-", distances[2][7][1])})
4	(s,0)	({if(distances[3][1][1]=9999,"-", nodenames[distances[3][1][0]])}, {if(distances[3][1][1]=9999,"-", distances[3][1][1])})	({if(distances[3][2][1]=9999,"-", nodenames[distances[3][2][0]])}, {if(distances[3][2][1]=9999,"-", distances[3][2][1])})	({if(distances[3][3][1]=9999,"-", nodenames[distances[3][3][0]])}, {if(distances[3][3][1]=9999,"-", distances[3][3][1])})	({if(distances[3][4][1]=9999,"-", nodenames[distances[3][4][0]])}, {if(distances[3][4][1]=9999,"-", distances[3][4][1])})	({if(distances[3][5][1]=9999,"-", nodenames[distances[3][5][0]])}, {if(distances[3][5][1]=9999,"-", distances[3][5][1])})	({if(distances[3][6][1]=9999,"-", nodenames[distances[3][6][0]])}, {if(distances[3][6][1]=9999,"-", distances[3][6][1])})	({if(distances[3][7][1]=9999,"-", nodenames[distances[3][7][0]])}, {if(distances[3][7][1]=9999,"-", distances[3][7][1])})
5	(s,0)	({if(distances[4][1][1]=9999,"-", nodenames[distances[4][1][0]])}, {if(distances[4][1][1]=9999,"-", distances[4][1][1])})	({if(distances[4][2][1]=9999,"-", nodenames[distances[4][2][0]])}, {if(distances[4][2][1]=9999,"-", distances[4][2][1])})	({if(distances[4][3][1]=9999,"-", nodenames[distances[4][3][0]])}, {if(distances[4][3][1]=9999,"-", distances[4][3][1])})	({if(distances[4][4][1]=9999,"-", nodenames[distances[4][4][0]])}, {if(distances[4][4][1]=9999,"-", distances[4][4][1])})	({if(distances[4][5][1]=9999,"-", nodenames[distances[4][5][0]])}, {if(distances[4][5][1]=9999,"-", distances[4][5][1])})	({if(distances[4][6][1]=9999,"-", nodenames[distances[4][6][0]])}, {if(distances[4][6][1]=9999,"-", distances[4][6][1])})	({if(distances[4][7][1]=9999,"-", nodenames[distances[4][7][0]])}, {if(distances[4][7][1]=9999,"-", distances[4][7][1])})
6	(s,0)	({if(distances[5][1][1]=9999,"-", nodenames[distances[5][1][0]])}, {if(distances[5][1][1]=9999,"-", distances[5][1][1])})	({if(distances[5][2][1]=9999,"-", nodenames[distances[5][2][0]])}, {if(distances[5][2][1]=9999,"-", distances[5][2][1])})	({if(distances[5][3][1]=9999,"-", nodenames[distances[5][3][0]])}, {if(distances[5][3][1]=9999,"-", distances[5][3][1])})	({if(distances[5][4][1]=9999,"-", nodenames[distances[5][4][0]])}, {if(distances[5][4][1]=9999,"-", distances[5][4][1])})	({if(distances[5][5][1]=9999,"-", nodenames[distances[5][5][0]])}, {if(distances[5][5][1]=9999,"-", distances[5][5][1])})	({if(distances[5][6][1]=9999,"-", nodenames[distances[5][6][0]])}, {if(distances[5][6][1]=9999,"-", distances[5][6][1])})	({if(distances[5][7][1]=9999,"-", nodenames[distances[5][7][0]])}, {if(distances[5][7][1]=9999,"-", distances[5][7][1])})
7	(s,0)	({if(distances[6][1][1]=9999,"-", nodenames[distances[6][1][0]])}, {if(distances[6][1][1]=9999,"-", distances[6][1][1])})	({if(distances[6][2][1]=9999,"-", nodenames[distances[6][2][0]])}, {if(distances[6][2][1]=9999,"-", distances[6][2][1])})	({if(distances[6][3][1]=9999,"-", nodenames[distances[6][3][0]])}, {if(distances[6][3][1]=9999,"-", distances[6][3][1])})	({if(distances[6][4][1]=9999,"-", nodenames[distances[6][4][0]])}, {if(distances[6][4][1]=9999,"-", distances[6][4][1])})	({if(distances[6][5][1]=9999,"-", nodenames[distances[6][5][0]])}, {if(distances[6][5][1]=9999,"-", distances[6][5][1])})	({if(distances[6][6][1]=9999,"-", nodenames[distances[6][6][0]])}, {if(distances[6][6][1]=9999,"-", distances[6][6][1])})	({if(distances[6][7][1]=9999,"-", nodenames[distances[6][7][0]])}, {if(distances[6][7][1]=9999,"-", distances[6][7][1])})

Give a worked solution to the whole question.

URL
URL

Text alternative
URL

Text alternative
URL

Text alternative
URL

Text alternative
URL

Text alternative

Use this tab to check that this question works as expected.

There was an error which means the tests can't run:

Part	Test	Passed?
Number entry
Number entry		Hasn't run yet

This question is not used in any exams.

Loading...

Error

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

Feedback

History

Comment

Checkpoint description

Stephen Maher 3 years, 4 months ago

Stephen Maher 3 years, 4 months ago

Stephen Maher 3 years, 4 months ago

Error in variable testing condition

Error

Warning

Generated value: `integer`

Parts

Number entry

Advanced settings

Loading...

Error

Dijkstra's Algorithm

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

Feedback

History

Comment

Checkpoint description

Stephen Maher 3 years, 4 months ago

Stephen Maher 3 years, 4 months ago

Stephen Maher 3 years, 4 months ago

Error in variable testing condition

Error

Warning

Generated value: integer

Parts

Number entry

Advanced settings

Generated value: `integer`