In a weighted graph $G$, the weight of a path is the sum of all edge weights in that path.
\nSuppose we fix a vertex $v_0$. A minimal $v_0$-spanning tree is a special spanning tree. Like all spanning trees there is a unique path from $v_0$ to any other vertex. But the special thing about this tree is that each of these paths is the shortest. The procedure to construct a minimal $v_0$-spanning tree is called Dijkstra's Algorithm:
\n1. Start by defining a tree $T=(V,E)$ which contains only the vertex $v_0$, i.e. $V = \\left\\{v_0\\right\\}$ and $E=\\left\\{\\right\\}$.
\n2. Consider all edges with one vertex in $V$ and the other vertex not in $V$:
\n$N = \\left\\{ [v,u] : v \\in V \\text{ and } u \\not \\in V\\right\\}$.
\n3. Find the edge $[u,v] \\in N$ which minimises the sum:
\n$|v_0,v| + \\operatorname{weight}([v,u])$.
\n4. Add $u$ to $V$ and add $[u,v]$ to $E$.
\n5. Repeat steps 2, 3 and 4 until $T$ is a spanning tree for $G$.
\nWhen constructed in this way, $(V,E)$ will be a minimal $v_0$-spanning tree.
", "advice": "Dijkstra's algorithm is described in detail above. If the answer-checker's feedback wasn't helpful to you, you could try performing the algorithm on a smaller/simpler graph of your own design for practice.
", "rulesets": {}, "extensions": ["jsxgraph"], "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true}, "constants": [], "variables": {"edges": {"name": "edges", "group": "Ungrouped variables", "definition": "[[0,1],[0,2],[1,2],[1,3],[2,3],[2,4],[3,4],[3,5],[4,5],[4,6],[5,7],[5,6],[6,7],[7,8],[6,8],[7,9],[8,9]]", "description": "", "templateType": "anything", "can_override": false}, "edgenames": {"name": "edgenames", "group": "Ungrouped variables", "definition": "keys(weights)", "description": "", "templateType": "anything", "can_override": false}, "dummyanswers": {"name": "dummyanswers", "group": "Ungrouped variables", "definition": "repeat(1,17)", "description": "", "templateType": "anything", "can_override": false}, "weights": {"name": "weights", "group": "Ungrouped variables", "definition": "[ \n \"v0,A\" : random(1..9),\n \"v0,B\" : random(1..9),\n \"A,B\" : random(1..9),\n \"A,C\" : random(1..9),\n \"B,C\" : random(1..9),\n \"B,D\" : random(1..9),\n \"C,D\" : random(1..9),\n \"C,E\" : random(1..9),\n \"D,E\" : random(1..9),\n \"D,F\" : random(1..9),\n \"E,G\" : random(1..9),\n \"E,F\" : random(1..9),\n \"F,G\" : random(1..9),\n \"G,H\" : random(1..9),\n \"F,H\" : random(1..9),\n \"G,v1\" : random(1..9),\n \"H,v1\" : random(1..9)\n]", "description": "", "templateType": "anything", "can_override": false}, "vertices": {"name": "vertices", "group": "Ungrouped variables", "definition": "[\"v0\",\"A\",\"B\",\"C\",\"D\",\"E\",\"F\",\"G\",\"H\",\"v1\"]", "description": "", "templateType": "anything", "can_override": false}}, "variablesTest": {"condition": "", "maxRuns": 100}, "ungrouped_variables": ["vertices", "edges", "weights", "edgenames", "dummyanswers"], "variable_groups": [], "functions": {"graph": {"parameters": [["V", "list"], ["E", "list"], ["weight", "dict"], ["edgenames", "list"]], "type": "html", "language": "javascript", "definition": "var div = Numbas.extensions.jsxgraph.makeBoard('600px','400px',\n{boundingBox: [-(2.5),(2),(3.5),0.1],\n axis: false,\n showNavigation: false,\n grid: false\n});\n\n \nvar board = div.board; \nvar n = V.length;\nvar points = []; // the javascript incarnation of vertices.\nvar lines = {};\n\npoints.push(board.create('point',[-2,1], {visible: true,name:V[0] + \":0\"}));\npoints.push(board.create('point',[-1.5,1.5], {visible: true,name:V[1]}));\npoints.push(board.create('point',[-1.5,0.5], {visible: true,name:V[2]}));\npoints.push(board.create('point',[-0.5,1.5], {visible: true,name:V[3]}));\npoints.push(board.create('point',[-0.5,0.5], {visible: true,name:V[4]}));\npoints.push(board.create('point',[0.5,1.5], {visible: true,name:V[5]}));\npoints.push(board.create('point',[0.5,0.5], {visible: true,name:V[6]}));\npoints.push(board.create('point',[1.5,1.5], {visible: true,name:V[7]}));\npoints.push(board.create('point',[1.5,0.5], {visible: true,name:V[8]}));\npoints.push(board.create('point',[2,1], {visible: true,name:V[9]}));\n\n// draw edges\nfor (var i = 0; i < E.length; i++) {\n var v1 = points[E[i][0]];\n var v2 = points[E[i][1]];\n var line = board.create('line',[v1,v2], {straightFirst:false, straightLast:false, strokeWidth:2});\n\n if (\"v0\" == v1.getAttribute(\"name\").split(\":\")[0]) {\n \n line.setAttribute({strokeWidth:4,strokeColor:'#008000'});\n }\n \n line.selected = false;\n board.create('midpoint', [line], {name: weight[edgenames[i]],size:0});\n var name = v1.getAttribute(\"name\").split(\":\")[0] + \",\" + v2.getAttribute(\"name\").split(\":\")[0];\n lines[name] = line;\n \n line.on('down',function(){\n var v1 = this.point1.getAttribute(\"name\").split(\":\")[0];\n var v2 = this.point2.getAttribute(\"name\").split(\":\")[0];\n var name = v1 + \",\" + v2;\n \n // if this is the first time that an edge has been selected, initiate the tree\n // init bug fix\n if (!Numbas.exam.currentQuestion.parts[0].tree) {\n Numbas.exam.currentQuestion.parts[0].tree = [];\n }\n \n switch(this.getAttribute(\"strokeColor\"))\n {\n case '#330000':\n // edge is black and already selected, unselect\n this.setAttribute({strokeWidth:2,strokeColor:'blue'});\n var i = Numbas.exam.currentQuestion.parts[0].tree.indexOf(name);\n Numbas.exam.currentQuestion.parts[0].tree.splice(i,1);\n this.selected = false;\n break;\n case '#008000':\n // edge is green and can be selected, select\n this.setAttribute({strokeWidth:5,strokeColor:'#330000'});\n Numbas.exam.currentQuestion.parts[0].tree.push(name);\n this.selected = true;\n break;\n case 'blue':\n // edge is blue and cannot be selected yet.\n alert(\"According to Dijkstra's algorithm this edge cannot be selected yet.\");\n }\n \n \n // recalculate distances\n // V is the set of vertices reached by the graph\n var V = new Set();\n V.add(\"v0\");\n var addedsomething;\n \n do {\n // loop through edges until there is nothing left to add.\n addedsomething = false;\n for (var i=0; i < Numbas.exam.currentQuestion.parts[0].tree.length; i++) {\n var e = Numbas.exam.currentQuestion.parts[0].tree[i];\n var u0 = e.split(\",\")[0];\n var u1 = e.split(\",\")[1];\n\n if (V.has(u0) && !V.has(u1)) {\n V.add(u1);\n addedsomething = true;\n } else if (!V.has(u0) && V.has(u1)) {\n V.add(u0);\n addedsomething = true;\n }\n }\n } while (addedsomething);\n\n \n // prune down the tree by removing any edge that is not connected to v0\n for (var i=0; i < Numbas.exam.currentQuestion.parts[0].tree.length; i++) {\n var e = Numbas.exam.currentQuestion.parts[0].tree[i];\n var u0 = e.split(\",\")[0];\n var u1 = e.split(\",\")[1];\n if (!V.has(u0) && !V.has(u1) ) {\n Numbas.exam.currentQuestion.parts[0].tree.splice(i,1);\n }\n }\n \n // answers are the definiatve list of shortest distances from v0\n var distance = {\"v0\":0};\n \n \n // calculate distances from v0 according to given subgraph \n var skip = 0;\n Numbas.exam.currentQuestion.parts[0].removeWarnings();\n while (Object.keys(distance).length + skip < V.size) {\n var neighbours = {};\n var addedEdge = false;\n for (var i=0; i < Numbas.exam.currentQuestion.parts[0].tree.length; i++) {\n var e = Numbas.exam.currentQuestion.parts[0].tree[i];\n for (var j = 0; j < 2; j++) {\n var u0 = e.split(\",\")[j % 2];\n var u1 = e.split(\",\")[(j+1) % 2];\n \n if (u0 in distance && !(u1 in distance)) {\n \n if (u1 in neighbours) {\n // the graph is a loop\n Numbas.exam.currentQuestion.parts[0].removeWarnings();\n Numbas.exam.currentQuestion.parts[0].giveWarning(\"Selection is not a tree.\");\n } else {\n // only one path seen so far to u1\n addedEdge = true;\n neighbours[u1] = distance[u0] + weight[e];\n \n }\n }\n } \n }\n if (!addedEdge) {\n // the edge has been disconnected from the tree\n skip++;\n Numbas.exam.currentQuestion.parts[0].removeWarnings();\n Numbas.exam.currentQuestion.parts[0].giveWarning(\"Edge $[\" + e + \"]$ is not connected to $v_0$.\");\n }\n \n // select minimum weight answer from all answers\n var min = 1000;\n var v;\n for (var k in neighbours) {\n if (neighbours[k] < min) {\n v = k;\n min = neighbours[k];\n }\n }\n if (min < 1000) {\n distance[v]=min;\n }\n }\n \n for (var i = 0; i < edgenames.length; i++) {\n var e = edgenames[i];\n \n var u0 = e.split(\",\")[0];\n var u1 = e.split(\",\")[1];\n \n if (V.has(u0) && V.has(u1)) {\n if (-1 !== Numbas.exam.currentQuestion.parts[0].tree.indexOf(e) ) {\n // edge is in the tree and should already be coloured black\n } else {\n // edge is not in the tree, but both start and end vertex are.\n // this edge would create a loop so mark it as unselected.\n lines[e].setAttribute({strokeWidth:2,strokeColor:'blue'});\n lines[e].selected = false;\n } \n } else if ((!V.has(u0) && V.has(u1)) || (V.has(u0) && !V.has(u1))) {\n // edge has one vertex in V and one not in V\n lines[e].setAttribute({strokeWidth:4,strokeColor:'#008000'});\n } else {\n // edge is not connected to the tree.\n lines[e].selected = false;\n lines[e].setAttribute({strokeWidth:2,strokeColor:'blue'});\n }\n }\n \n Numbas.exam.currentQuestion.parts[0].distance = distance;\n \n // update graph display of distance \n for (var i = 0; i < points.length; i++) {\n var vertex = points[i].getAttribute(\"name\").split(\":\")[0];\n if (vertex in distance) {\n points[i].setAttribute({\"name\" : (vertex + \":\" + distance[vertex])});\n } else {\n points[i].setAttribute({\"name\" : (vertex)});\n }\n }\n \n \n });\n}\n\nreturn div;"}}, "preamble": {"js": "\n// perform dijkstra's algorithm on subgraph with given weights.\n// return dictionary of minimum distances from v0.\ncalculateDistance = function(subgraph, weight){\n \n \n // the set of vertices reached by the graph\n var V = new Set();\n for (var i=0; i < subgraph.length; i++) {\n var e = subgraph[i];\n var u0 = e.split(\",\")[0];\n var u1 = e.split(\",\")[1];\n V.add(u0);\n V.add(u1);\n }\n \n // answers are the definiatve list of shortest distances from v0\n var answers = {\"v0\":0};\n \n // calculate distances from v0 according to given subgraph \n var skip = 0;\n while (Object.keys(answers).length + skip < V.size) {\n var neighbours = {};\n var addedSomething = false;\n for (var i=0; i < subgraph.length; i++) {\n var e = subgraph[i];\n for (var j = 0; j < 2; j++) {\n var u0 = e.split(\",\")[j % 2];\n var u1 = e.split(\",\")[(j+1) % 2];\n \n if (u0 in answers && !(u1 in answers)) {\n addedSomething = true;\n if (u1 in neighbours) {\n // take the shortest path from all seen paths\n neighbours[u1] = Math.min(answers[u0] + weight[e],neighbours[u1]);\n } else {\n // only one path seen so far to u1\n neighbours[u1] = answers[u0] + weight[e];\n }\n }\n } \n }\n if (!addedSomething) {\n skip++;\n }\n \n // select minimum weight answer from all answers\n var min = 1000;\n var v;\n for (var k in neighbours) {\n if (neighbours[k] < min) {\n v = k;\n min = neighbours[k];\n }\n }\n if (min < 1000) {\n answers[v]=min;\n }\n \n } \n return answers; \n}\n", "css": ""}, "parts": [{"type": "extension", "useCustomName": false, "customName": "", "marks": "12", "scripts": {"constructor": {"script": "\nthis.tree = [];\n\n// calculate distance from v0 to each vertex in TV\nthis.distance = {\"v0\": 0};\nthis.marks = 6;\n\nvar variables = this.question.scope.variables;\nvar unwrap = Numbas.jme.unwrapValue;\nvar weight = unwrap(variables.weights);\nvar vertices = unwrap(variables.vertices);\nvar edgenames = unwrap(variables.edgenames);\n\nthis.answers = calculateDistance(edgenames, weight);\n", "order": "after"}, "mark": {"script": "var variables = this.question.scope.variables;\nvar unwrap = Numbas.jme.unwrapValue;\nvar weight = unwrap(variables.weights);\nvar vertices = unwrap(variables.vertices);\nvar edgenames = unwrap(variables.edgenames);\n\nthis.answers = calculateDistance(edgenames, weight);\nvar allgood = true;\n\n// compare student answer (distance) to answers\nfor (var v in this.answers) {\n if (v in this.distance) {\n if (this.answers[v] == this.distance[v]) {\n this.addCredit(0.1,\"Distance $\" + this.distance[v] + \"$ to vertex $\" +v+ \"$ is minimal\");\n } else {\n this.addCredit(0,\"Distance $\" + this.distance[v] + \"$ to vertex $\" +v+ \"$ is not minimal. Hint: look for a path of length $\" + this.answers[v] +\"$.\");\n allgood = false;\n }\n } else {\n this.addCredit(0,\"Tree does not reach vertex $\" +v+ \"$.\");\n allgood = false;\n } \n}\n\nif (allgood) {\n this.setCredit(1);\n}", "order": "instead"}, "validate": {"script": "// check every vertex is reachable\nvar variables = this.question.scope.variables;\nvar unwrap = Numbas.jme.unwrapValue;\nvar vertices = unwrap(variables.vertices);\nvar edgenames = unwrap(variables.edgenames);\n\nthis.removeWarnings();\n\nfor (var i = 0; i < vertices.length; i++) {\n var v = vertices[i];\n if (!(v in this.distance)) {\n this.giveWarning(\"vertex $\"+v+\"$ is not connected to $v_0$.\");\n return true;\n }\n}\n\nif (this.tree.length >= vertices.length) {\n this.giveWarning(\"Too many edges selected.\");\n return false; \n}\n\nreturn true;\n", "order": "instead"}}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "Perform Dijkstra's algorithm on the following graph.
\n{graph(vertices,edges,weights,edgenames)}
\n\u200b
\n"}], "partsMode": "all", "maxMarks": 0, "objectives": [], "penalties": [], "objectiveVisibility": "always", "penaltyVisibility": "always", "type": "question", "contributors": [{"name": "Daniel Mansfield", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/743/"}, {"name": "Joshua Capel", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/1479/"}, {"name": "Sean Gardiner", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/2443/"}]}]}], "contributors": [{"name": "Daniel Mansfield", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/743/"}, {"name": "Joshua Capel", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/1479/"}, {"name": "Sean Gardiner", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/2443/"}]}