// Numbas version: exam_results_page_options
{"name": "Find the shortest path", "extensions": [], "custom_part_types": [], "resources": [["question-resources/network2_P9Gdj38.svg", "/srv/numbas/media/question-resources/network2_P9Gdj38.svg"]], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"name": "Find the shortest path", "tags": [], "metadata": {"description": "<p>Students are shown a graph with 6 vertices and asked to find the length of the shortest path from A to a random vertex.</p>\n<p>There is only one graph, but all of the weights are randomised.</p>\n<p>They can find the length any way they wish. In the advice, the steps of Dijkstra's algorithm used in solving this problem are displayed. It is not a complete worked solution but it should be sufficient to figure out the shortest path used to reach each vertex.</p>", "licence": "All rights reserved"}, "statement": "<p>Consider the following network:</p>\n<p><img src=\"resources/question-resources/network2_P9Gdj38.svg\"/></p>", "advice": "<p>You can either work out the shortest path by looking at the graph and figuring it out, or by using Dijkstra's algorithm.</p>\n<p>The length of the shortest path is calculated by adding up the weights along the shortest path.</p>\n<p></p>\n<p>The computer used Dijkstra's algorithm to find a shortest path.</p>\n<p>Here are the shortest distances from A to each vertex that it calculated in each step of the algorithm. You can use this to help you find the shortest path.</p>\n<p>A&nbsp;blank entry&nbsp;means that the algorithm has not yet added that vertex to the&nbsp;shortest path tree.</p>\n<table border=\"|\" cellpadding=\"10\" cellspacing=\"10\" style=\"margin-left: auto; margin-right: auto; border-color: #000000;\">\n<tbody>\n<tr>\n<td><strong>Step No</strong></td>\n<td>A</td>\n<td>B</td>\n<td>C</td>\n<td>D</td>\n<td>E</td>\n<td>F</td>\n</tr>\n<tr>\n<td>1</td>\n<td>0</td>\n<td>{if(distarray[0][1]=99,\"\",distarray[0][1])}</td>\n<td>{if(distarray[0][2]=99,\"\",distarray[0][2])}</td>\n<td>{if(distarray[0][3]=99,\"\",distarray[0][3])}</td>\n<td>{if(distarray[0][4]=99,\"\",distarray[0][4])}</td>\n<td>{if(distarray[0][5]=99,\"\",distarray[0][5])}</td>\n</tr>\n<tr>\n<td>2</td>\n<td>0</td>\n<td>{if(distarray[1][1]=99,\"\",distarray[1][1])}</td>\n<td>{if(distarray[1][2]=99,\"\",distarray[1][2])}</td>\n<td>{if(distarray[1][3]=99,\"\",distarray[1][3])}</td>\n<td>{if(distarray[1][4]=99,\"\",distarray[1][4])}</td>\n<td>{if(distarray[1][5]=99,\"\",distarray[1][5])}</td>\n</tr>\n<tr>\n<td>3</td>\n<td>0</td>\n<td>{if(distarray[2][1]=99,\"\",distarray[2][1])}</td>\n<td>{if(distarray[2][2]=99,\"\",distarray[2][2])}</td>\n<td>{if(distarray[2][3]=99,\"\",distarray[2][3])}</td>\n<td>{if(distarray[2][4]=99,\"\",distarray[2][4])}</td>\n<td>{if(distarray[2][5]=99,\"\",distarray[2][5])}</td>\n</tr>\n<tr>\n<td>4</td>\n<td>0</td>\n<td>{if(distarray[3][1]=99,\"\",distarray[3][1])}</td>\n<td>{if(distarray[3][2]=99,\"\",distarray[3][2])}</td>\n<td>{if(distarray[3][3]=99,\"\",distarray[3][3])}</td>\n<td>{if(distarray[3][4]=99,\"\",distarray[3][4])}</td>\n<td>{if(distarray[3][5]=99,\"\",distarray[3][5])}</td>\n</tr>\n<tr>\n<td>5</td>\n<td>0</td>\n<td>{if(distarray[4][1]=99,\"\",distarray[4][1])}</td>\n<td>{if(distarray[4][2]=99,\"\",distarray[4][2])}</td>\n<td>{if(distarray[4][3]=99,\"\",distarray[4][3])}</td>\n<td>{if(distarray[4][4]=99,\"\",distarray[4][4])}</td>\n<td>{if(distarray[4][5]=99,\"\",distarray[4][5])}</td>\n</tr>\n<tr>\n<td>6</td>\n<td>0</td>\n<td>{if(distarray[5][1]=99,\"\",distarray[5][1])}</td>\n<td>{if(distarray[5][2]=99,\"\",distarray[5][2])}</td>\n<td>{if(distarray[5][3]=99,\"\",distarray[5][3])}</td>\n<td>{if(distarray[5][4]=99,\"\",distarray[5][4])}</td>\n<td>{if(distarray[5][5]=99,\"\",distarray[5][5])}</td>\n</tr>\n</tbody>\n</table>\n<p></p>", "rulesets": {}, "extensions": [], "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true}, "constants": [], "variables": {"AB": {"name": "AB", "group": "Ungrouped variables", "definition": "random(1..10)", "description": "", "templateType": "anything", "can_override": false}, "AC": {"name": "AC", "group": "Ungrouped variables", "definition": "random(1..10)", "description": "", "templateType": "anything", "can_override": false}, "AE": {"name": "AE", "group": "Ungrouped variables", "definition": "random(1..10)", "description": "", "templateType": "anything", "can_override": false}, "BC": {"name": "BC", "group": "Ungrouped variables", "definition": "random(1..10)", "description": "", "templateType": "anything", "can_override": false}, "BE": {"name": "BE", "group": "Ungrouped variables", "definition": "random(1..10)", "description": "", "templateType": "anything", "can_override": false}, "BF": {"name": "BF", "group": "Ungrouped variables", "definition": "random(1..10)", "description": "", "templateType": "anything", "can_override": false}, "CD": {"name": "CD", "group": "Ungrouped variables", "definition": "random(1..10)", "description": "", "templateType": "anything", "can_override": false}, "CE": {"name": "CE", "group": "Ungrouped variables", "definition": "random(1..10)", "description": "", "templateType": "anything", "can_override": false}, "CF": {"name": "CF", "group": "Ungrouped variables", "definition": "random(1..10)", "description": "", "templateType": "anything", "can_override": false}, "DE": {"name": "DE", "group": "Ungrouped variables", "definition": "random(1..10)", "description": "", "templateType": "anything", "can_override": false}, "DF": {"name": "DF", "group": "Ungrouped variables", "definition": "random(1..10)", "description": "", "templateType": "anything", "can_override": false}, "EF": {"name": "EF", "group": "Ungrouped variables", "definition": "random(1..10)", "description": "", "templateType": "anything", "can_override": false}, "AD": {"name": "AD", "group": "Ungrouped variables", "definition": "99", "description": "", "templateType": "anything", "can_override": false}, "AF": {"name": "AF", "group": "Ungrouped variables", "definition": "99", "description": "", "templateType": "anything", "can_override": false}, "BD": {"name": "BD", "group": "Ungrouped variables", "definition": "99", "description": "", "templateType": "anything", "can_override": false}, "endlist": {"name": "endlist", "group": "Ungrouped variables", "definition": "[\"C\",\"D\",\"F\"]", "description": "", "templateType": "anything", "can_override": false}, "endchoice": {"name": "endchoice", "group": "Ungrouped variables", "definition": "random(0,1,2)", "description": "", "templateType": "anything", "can_override": false}, "end": {"name": "end", "group": "Ungrouped variables", "definition": "endlist[endchoice]", "description": "", "templateType": "anything", "can_override": false}, "weights": {"name": "weights", "group": "Ungrouped variables", "definition": "[\n  [99,AB,AC,AD,AE,AF],\n  [AB,99,BC,BD,BE,BF],\n  [AC,BC,99,CD,CE,CF],\n  [AD,BD,CD,99,DE,DF],\n  [AE,BE,CE,DE,99,EF],\n  [AF,BF,CF,DF,EF,99]\n  ]", "description": "", "templateType": "anything", "can_override": false}, "distances": {"name": "distances", "group": "Ungrouped variables", "definition": "[distarray[5][2],distarray[5][3],distarray[5][5]]", "description": "", "templateType": "anything", "can_override": false}, "answer": {"name": "answer", "group": "Ungrouped variables", "definition": "distances[endchoice]", "description": "", "templateType": "anything", "can_override": false}, "distarray": {"name": "distarray", "group": "Ungrouped variables", "definition": "dijkstra(weights)", "description": "", "templateType": "anything", "can_override": false}}, "variablesTest": {"condition": "", "maxRuns": 100}, "ungrouped_variables": ["AB", "AC", "AE", "BC", "BE", "BF", "CD", "CE", "CF", "DE", "DF", "EF", "AD", "AF", "BD", "endlist", "endchoice", "end", "weights", "distances", "answer", "distarray"], "variable_groups": [], "functions": {"dijkstra": {"parameters": [["weights", "?"]], "type": "number", "language": "javascript", "definition": "var distarray = [[99,99,99,99,99,99],[99,99,99,99,99,99],[99,99,99,99,99,99],[99,99,99,99,99,99],[99,99,99,99,99,99],[99,99,99,99,99,99]];\n\n// S is the set in the tree\nvar S = [0];\n\n// out  is the set outside the tree\nvar out = [1,2,3,4,5];\n\n// distances is the shortest distance from A to each vertex\nvar distances = [0,99,99,99,99,99];\n  for (t=0;t<6;t++){\n\tdistarray[0][t] = distances[t];\n    }\n// Find the vertex closest to A\nvar least = Math.min(...weights[0]);\nvar idx1 = 0;\nvar idx2 = weights[0].indexOf(least);\n\n// Move that vertex into S\n  \tS.push(idx2);\n\tout.splice(out.indexOf(idx2),1);\n\n// Update the distances\ndistances[idx2]=weights[0][idx2];\nfor (t=0;t<6;t++){\n\tdistarray[1][t] = distances[t];\n    }\n// Now we want to check all the edges from S to out.\n// for each element in S build a set of the weights from it to elements in out.\n\nfor (k=2;k<6;k++){\n\nvar wtarray = [];\n\nfor(j=0;j<out.length;j++){\n\tfor (i=0;i<S.length;i++){\n    \twtarray.push(weights[S[i]][out[j]]+distances[S[i]]);\n    }\n}\n\n// choose the smallest element. Add its vertex to S and update the distance.\nvar newdist = Math.min(...wtarray);\nidx1 = wtarray.indexOf(newdist);\nidx2 = Math.floor(idx1/k); // this is the index of the element in out to   move.\n\n// Update the distances\n  distances[out[idx2]]=newdist;\nfor (t=0;t<6;t++){\n\tdistarray[k][t] = distances[t];\n    }\n// Move that vertex into S\n  \tS.push(out[idx2]);\n\tout.splice(idx2,1);\n\n}\n\nreturn distarray;"}}, "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": "<p>Find the shortest path from A to {end}.</p>", "minValue": "answer", "maxValue": "answer", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "displayAnswer": "", "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}], "partsMode": "all", "maxMarks": 0, "objectives": [], "penalties": [], "objectiveVisibility": "always", "penaltyVisibility": "always", "contributors": [{"name": "Merryn Horrocks", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/4052/"}]}]}], "contributors": [{"name": "Merryn Horrocks", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/4052/"}]}