// 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

\n

with the edge weights

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
abcdefgh
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}
\n

", "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.

\n

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}).

\n

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.

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
Stepabcdefgh
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])})
\n

", "rulesets": {}, "extensions": [], "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true}, "constants": [], "variables": {"ab": {"name": "ab", "group": "Ungrouped variables", "definition": "random(1..maxweight)", "description": "", "templateType": "anything", "can_override": false}, "ac": {"name": "ac", "group": "Ungrouped variables", "definition": "random(1..maxweight)", "description": "", "templateType": "anything", "can_override": false}, "ad": {"name": "ad", "group": "Ungrouped variables", "definition": "random(1..maxweight)", "description": "", "templateType": "anything", "can_override": false}, "ae": {"name": "ae", "group": "Ungrouped variables", "definition": "random(1..maxweight)", "description": "", "templateType": "anything", "can_override": false}, "bc": {"name": "bc", "group": "Ungrouped variables", "definition": "random(1..maxweight)", "description": "", "templateType": "anything", "can_override": false}, "bf": {"name": "bf", "group": "Ungrouped variables", "definition": "random(1..maxweight)", "description": "", "templateType": "anything", "can_override": false}, "ce": {"name": "ce", "group": "Ungrouped variables", "definition": "random(1..maxweight)", "description": "", "templateType": "anything", "can_override": false}, "cg": {"name": "cg", "group": "Ungrouped variables", "definition": "random(1..maxweight)", "description": "", "templateType": "anything", "can_override": false}, "de": {"name": "de", "group": "Ungrouped variables", "definition": "random(1..maxweight)", "description": "", "templateType": "anything", "can_override": false}, "df": {"name": "df", "group": "Ungrouped variables", "definition": "random(1..maxweight)", "description": "", "templateType": "anything", "can_override": false}, "dg": {"name": "dg", "group": "Ungrouped variables", "definition": "random(1..maxweight)", "description": "", "templateType": "anything", "can_override": false}, "eg": {"name": "eg", "group": "Ungrouped variables", "definition": "random(1..maxweight)", "description": "", "templateType": "anything", "can_override": false}, "fg": {"name": "fg", "group": "Ungrouped variables", "definition": "random(1..maxweight)", "description": "", "templateType": "anything", "can_override": false}, "sinkoptions": {"name": "sinkoptions", "group": "Ungrouped variables", "definition": "['f', 'g', 'h']", "description": "", "templateType": "anything", "can_override": false}, "sinkchoice": {"name": "sinkchoice", "group": "Ungrouped variables", "definition": "random(0, 1,2)", "description": "", "templateType": "anything", "can_override": false}, "sink": {"name": "sink", "group": "Ungrouped variables", "definition": "sinkoptions[sinkchoice]", "description": "", "templateType": "anything", "can_override": false}, "edgeweights": {"name": "edgeweights", "group": "Ungrouped variables", "definition": "[[9999,ab,ac,ad,9999,9999,9999,9999],\n[ab,9999,bc,9999,9999,bf,9999,9999],\n[ac,bc,9999,9999,ce,9999,9999,ch],\n[ad,9999,9999,9999,de,df,9999,9999],\n[9999,9999,ce,de,9999,9999,eg,eh],\n[9999,bf,9999,df,9999,9999,fg,9999],\n[9999,9999,9999,9999,eg,fg,9999,gh],\n[9999,9999,ch,9999,eh,9999,gh,9999],]", "description": "", "templateType": "anything", "can_override": false}, "shortestdist": {"name": "shortestdist", "group": "Ungrouped variables", "definition": "[distances[6][5][1], distances[6][6][1], distances[6][7][1]]", "description": "", "templateType": "anything", "can_override": false}, "distances": {"name": "distances", "group": "Ungrouped variables", "definition": "find_shortest_path(edgeweights, numnodes)", "description": "", "templateType": "anything", "can_override": false}, "answer": {"name": "answer", "group": "Ungrouped variables", "definition": "shortestdist[sinkchoice]", "description": "", "templateType": "anything", "can_override": false}, "nodenames": {"name": "nodenames", "group": "Ungrouped variables", "definition": "['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']", "description": "", "templateType": "anything", "can_override": false}, "numnodes": {"name": "numnodes", "group": "Ungrouped variables", "definition": "len(nodenames)", "description": "", "templateType": "anything", "can_override": false}, "ch": {"name": "ch", "group": "Ungrouped variables", "definition": "random(1..maxweight)", "description": "", "templateType": "anything", "can_override": false}, "eh": {"name": "eh", "group": "Ungrouped variables", "definition": "random(1..maxweight)", "description": "", "templateType": "anything", "can_override": false}, "gh": {"name": "gh", "group": "Ungrouped variables", "definition": "random(1..maxweight)", "description": "", "templateType": "anything", "can_override": false}, "maxweight": {"name": "maxweight", "group": "Ungrouped variables", "definition": "5", "description": "", "templateType": "anything", "can_override": false}}, "variablesTest": {"condition": "", "maxRuns": 100}, "ungrouped_variables": ["ab", "ac", "ad", "ae", "bc", "bf", "ce", "cg", "de", "df", "dg", "eg", "fg", "sinkoptions", "sinkchoice", "sink", "edgeweights", "shortestdist", "distances", "answer", "nodenames", "numnodes", "ch", "eh", "gh", "maxweight"], "variable_groups": [], "functions": {"find_shortest_path": {"parameters": [["edgeweights", "?"], ["numnodes", "number"]], "type": "anything", "language": "javascript", "definition": "// initialising the predecessor/distance array\nvar preddist = []\nfor (i=0; i < numnodes; i++){\n var algstep = []\n for (j = 0; j < numnodes; j++){\n if (i == 0 && j == 0){\n algstep.push([-1, 0])\n }\n else{\n algstep.push([-1, 9999])\n }\n }\n preddist.push(algstep)\n}\n\n// creating the unvisited list\nvar unvisited = []\nfor (i = 0; i < numnodes; i++){\n unvisited.push(i)\n}\n\n// performing Dijkstra's algorithm.\n// Since there are 7 nodes, then we need to perform 6 steps to find the shortest path to all nodes\nfor (i = 0; i < numnodes - 1; i++){\n // copying the predecessors and distances from the previous iteration to the current iteration\n if (i > 0){\n for (j = 0; j < numnodes; j++){\n preddist[i][j][0] = preddist[i - 1][j][0]\n preddist[i][j][1] = preddist[i - 1][j][1]\n }\n }\n \n // finding the next unvisited node\n var mindist = 9999\n var unvisitedidx = -1\n for (j = 0; j < unvisited.length; j++){\n if (preddist[i][unvisited[j]][1] < mindist){\n mindist = preddist[i][unvisited[j]][1]\n unvisitedidx = j\n }\n }\n \n var currnode = unvisited[unvisitedidx]\n var currdist = preddist[i][currnode][1]\n \n // updating the distances to the connected nodes\n for (j = 0; j < numnodes; j++){\n if (j == currnode){\n continue\n }\n \n var disttonode = currdist + edgeweights[currnode][j]\n \n // updating the distance to the node\n if (disttonode < preddist[i][j][1]){\n preddist[i][j][1] = disttonode\n preddist[i][j][0] = currnode\n }\n }\n \n // removing the current node from the unvisited nodes\n unvisited[unvisitedidx] = unvisited[unvisited.length - 1]\n unvisited.pop()\n}\n\nreturn preddist"}}, "preamble": {"js": "", "css": ""}, "parts": [{"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "

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/"}]}