// Numbas version: exam_results_page_options {"name": "Dijkstra's Algorithm", "extensions": [], "custom_part_types": [], "resources": [["question-resources/undirected_graph.pdf", "/srv/numbas/media/question-resources/undirected_graph.pdf"], ["question-resources/undirected_graph.svg", "/srv/numbas/media/question-resources/undirected_graph.svg"], ["question-resources/undirected_graph_tIIsQgg.svg", "/srv/numbas/media/question-resources/undirected_graph_tIIsQgg.svg"], ["question-resources/undirected_graph_8aOAR1y.svg", "/srv/numbas/media/question-resources/undirected_graph_8aOAR1y.svg"], ["question-resources/undirected_graph_7tDXAzq.svg", "/srv/numbas/media/question-resources/undirected_graph_7tDXAzq.svg"], ["question-resources/undirected_graph_FwFHTj6.svg", "/srv/numbas/media/question-resources/undirected_graph_FwFHTj6.svg"]], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"name": "Dijkstra's Algorithm", "tags": [], "metadata": {"description": "
Attempt to apply Dijkstra's algorithm to find the shortest path from the source node (a) to a given sink node.
", "licence": "Creative Commons Attribution 4.0 International"}, "statement": "Consider the undirected graph
\n\nwith the edge weights
\n\n | a | \nb | \nc | \nd | \ne | \nf | \ng | \nh | \n
a | \n\n | {ab} | \n{ac} | \n{ad} | \n\n | \n | \n | \n |
b | \n{ab} | \n\n | {bc} | \n\n | \n | {bf} | \n\n | \n |
c | \n{ac} | \n{bc} | \n\n | \n | {ce} | \n\n | \n | {ch} | \n
d | \n{ad} | \n\n | \n | \n | {de} | \n{df} | \n\n | \n |
e | \n\n | \n | {ce} | \n{de} | \n\n | \n | {eg} | \n{eh} | \n
f | \n\n | {bf} | \n\n | {df} | \n\n | \n | {fg} | \n\n |
g | \n\n | \n | \n | \n | {eg} | \n{fg} | \n\n | {gh} | \n
h | \n\n | \n | {ch} | \n\n | {eh} | \n\n | {gh} | \n\n |
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.
\nThe 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}).
\nBelow 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.
\nStep | \na | \nb | \nc | \nd | \ne | \nf | \ng | \nh | \n
1 | \n(s,0) | \n({if(distances[0][1][1]=9999,\"-\", nodenames[distances[0][1][0]])}, {if(distances[0][1][1]=9999,\"-\", distances[0][1][1])}) | \n({if(distances[0][2][1]=9999,\"-\", nodenames[distances[0][2][0]])}, {if(distances[0][2][1]=9999,\"-\", distances[0][2][1])}) | \n({if(distances[0][3][1]=9999,\"-\", nodenames[distances[0][3][0]])}, {if(distances[0][3][1]=9999,\"-\", distances[0][3][1])}) | \n({if(distances[0][4][1]=9999,\"-\", nodenames[distances[0][4][0]])}, {if(distances[0][4][1]=9999,\"-\", distances[0][4][1])}) | \n({if(distances[0][5][1]=9999,\"-\", nodenames[distances[0][5][0]])}, {if(distances[0][5][1]=9999,\"-\", distances[0][5][1])}) | \n({if(distances[0][6][1]=9999,\"-\", nodenames[distances[0][6][0]])}, {if(distances[0][6][1]=9999,\"-\", distances[1][6][1])}) | \n({if(distances[0][7][1]=9999,\"-\", nodenames[distances[0][7][0]])}, {if(distances[0][7][1]=9999,\"-\", distances[1][7][1])}) | \n
2 | \n(s,0) | \n({if(distances[1][1][1]=9999,\"-\", nodenames[distances[1][1][0]])}, {if(distances[1][1][1]=9999,\"-\", distances[1][1][1])}) | \n({if(distances[1][2][1]=9999,\"-\", nodenames[distances[1][2][0]])}, {if(distances[1][2][1]=9999,\"-\", distances[1][2][1])}) | \n({if(distances[1][3][1]=9999,\"-\", nodenames[distances[1][3][0]])}, {if(distances[1][3][1]=9999,\"-\", distances[1][3][1])}) | \n({if(distances[1][4][1]=9999,\"-\", nodenames[distances[1][4][0]])}, {if(distances[1][4][1]=9999,\"-\", distances[1][4][1])}) | \n({if(distances[1][5][1]=9999,\"-\", nodenames[distances[1][5][0]])}, {if(distances[1][5][1]=9999,\"-\", distances[1][5][1])}) | \n({if(distances[1][6][1]=9999,\"-\", nodenames[distances[1][6][0]])}, {if(distances[1][6][1]=9999,\"-\", distances[1][6][1])}) | \n({if(distances[1][7][1]=9999,\"-\", nodenames[distances[1][7][0]])}, {if(distances[1][7][1]=9999,\"-\", distances[1][7][1])}) | \n
3 | \n(s,0) | \n({if(distances[2][1][1]=9999,\"-\", nodenames[distances[2][1][0]])}, {if(distances[2][1][1]=9999,\"-\", distances[2][1][1])}) | \n({if(distances[2][2][1]=9999,\"-\", nodenames[distances[2][2][0]])}, {if(distances[2][2][1]=9999,\"-\", distances[2][2][1])}) | \n({if(distances[2][3][1]=9999,\"-\", nodenames[distances[2][3][0]])}, {if(distances[2][3][1]=9999,\"-\", distances[2][3][1])}) | \n({if(distances[2][4][1]=9999,\"-\", nodenames[distances[2][4][0]])}, {if(distances[2][4][1]=9999,\"-\", distances[2][4][1])}) | \n({if(distances[2][5][1]=9999,\"-\", nodenames[distances[2][5][0]])}, {if(distances[2][5][1]=9999,\"-\", distances[2][5][1])}) | \n({if(distances[2][6][1]=9999,\"-\", nodenames[distances[2][6][0]])}, {if(distances[2][6][1]=9999,\"-\", distances[2][6][1])}) | \n({if(distances[2][7][1]=9999,\"-\", nodenames[distances[2][7][0]])}, {if(distances[2][7][1]=9999,\"-\", distances[2][7][1])}) | \n
4 | \n(s,0) | \n({if(distances[3][1][1]=9999,\"-\", nodenames[distances[3][1][0]])}, {if(distances[3][1][1]=9999,\"-\", distances[3][1][1])}) | \n({if(distances[3][2][1]=9999,\"-\", nodenames[distances[3][2][0]])}, {if(distances[3][2][1]=9999,\"-\", distances[3][2][1])}) | \n({if(distances[3][3][1]=9999,\"-\", nodenames[distances[3][3][0]])}, {if(distances[3][3][1]=9999,\"-\", distances[3][3][1])}) | \n({if(distances[3][4][1]=9999,\"-\", nodenames[distances[3][4][0]])}, {if(distances[3][4][1]=9999,\"-\", distances[3][4][1])}) | \n({if(distances[3][5][1]=9999,\"-\", nodenames[distances[3][5][0]])}, {if(distances[3][5][1]=9999,\"-\", distances[3][5][1])}) | \n({if(distances[3][6][1]=9999,\"-\", nodenames[distances[3][6][0]])}, {if(distances[3][6][1]=9999,\"-\", distances[3][6][1])}) | \n({if(distances[3][7][1]=9999,\"-\", nodenames[distances[3][7][0]])}, {if(distances[3][7][1]=9999,\"-\", distances[3][7][1])}) | \n
5 | \n(s,0) | \n({if(distances[4][1][1]=9999,\"-\", nodenames[distances[4][1][0]])}, {if(distances[4][1][1]=9999,\"-\", distances[4][1][1])}) | \n({if(distances[4][2][1]=9999,\"-\", nodenames[distances[4][2][0]])}, {if(distances[4][2][1]=9999,\"-\", distances[4][2][1])}) | \n({if(distances[4][3][1]=9999,\"-\", nodenames[distances[4][3][0]])}, {if(distances[4][3][1]=9999,\"-\", distances[4][3][1])}) | \n({if(distances[4][4][1]=9999,\"-\", nodenames[distances[4][4][0]])}, {if(distances[4][4][1]=9999,\"-\", distances[4][4][1])}) | \n({if(distances[4][5][1]=9999,\"-\", nodenames[distances[4][5][0]])}, {if(distances[4][5][1]=9999,\"-\", distances[4][5][1])}) | \n({if(distances[4][6][1]=9999,\"-\", nodenames[distances[4][6][0]])}, {if(distances[4][6][1]=9999,\"-\", distances[4][6][1])}) | \n({if(distances[4][7][1]=9999,\"-\", nodenames[distances[4][7][0]])}, {if(distances[4][7][1]=9999,\"-\", distances[4][7][1])}) | \n
6 | \n(s,0) | \n({if(distances[5][1][1]=9999,\"-\", nodenames[distances[5][1][0]])}, {if(distances[5][1][1]=9999,\"-\", distances[5][1][1])}) | \n({if(distances[5][2][1]=9999,\"-\", nodenames[distances[5][2][0]])}, {if(distances[5][2][1]=9999,\"-\", distances[5][2][1])}) | \n({if(distances[5][3][1]=9999,\"-\", nodenames[distances[5][3][0]])}, {if(distances[5][3][1]=9999,\"-\", distances[5][3][1])}) | \n({if(distances[5][4][1]=9999,\"-\", nodenames[distances[5][4][0]])}, {if(distances[5][4][1]=9999,\"-\", distances[5][4][1])}) | \n({if(distances[5][5][1]=9999,\"-\", nodenames[distances[5][5][0]])}, {if(distances[5][5][1]=9999,\"-\", distances[5][5][1])}) | \n({if(distances[5][6][1]=9999,\"-\", nodenames[distances[5][6][0]])}, {if(distances[5][6][1]=9999,\"-\", distances[5][6][1])}) | \n({if(distances[5][7][1]=9999,\"-\", nodenames[distances[5][7][0]])}, {if(distances[5][7][1]=9999,\"-\", distances[5][7][1])}) | \n
7 | \n(s,0) | \n({if(distances[6][1][1]=9999,\"-\", nodenames[distances[6][1][0]])}, {if(distances[6][1][1]=9999,\"-\", distances[6][1][1])}) | \n({if(distances[6][2][1]=9999,\"-\", nodenames[distances[6][2][0]])}, {if(distances[6][2][1]=9999,\"-\", distances[6][2][1])}) | \n({if(distances[6][3][1]=9999,\"-\", nodenames[distances[6][3][0]])}, {if(distances[6][3][1]=9999,\"-\", distances[6][3][1])}) | \n({if(distances[6][4][1]=9999,\"-\", nodenames[distances[6][4][0]])}, {if(distances[6][4][1]=9999,\"-\", distances[6][4][1])}) | \n({if(distances[6][5][1]=9999,\"-\", nodenames[distances[6][5][0]])}, {if(distances[6][5][1]=9999,\"-\", distances[6][5][1])}) | \n({if(distances[6][6][1]=9999,\"-\", nodenames[distances[6][6][0]])}, {if(distances[6][6][1]=9999,\"-\", distances[6][6][1])}) | \n({if(distances[6][7][1]=9999,\"-\", nodenames[distances[6][7][0]])}, {if(distances[6][7][1]=9999,\"-\", distances[6][7][1])}) | \n
Find the shortest path from (a) to ({sink})
", "minValue": "answer", "maxValue": "answer", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}], "partsMode": "all", "maxMarks": 0, "objectives": [], "penalties": [], "objectiveVisibility": "always", "penaltyVisibility": "always", "contributors": [{"name": "Stephen Maher", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/9339/"}]}]}], "contributors": [{"name": "Stephen Maher", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/9339/"}]}