2d:null 2e:["$","title",null,{"children":"A short explanation of Dijkstra’s shortest paths algorithm | Michael Arntzenius | Observable"}] 33:T49f,html`

CSS & display code

`34:Tf87,drawDijkstra = (graph, state) => { let lineHeight = 1.75 * queueFontSize; let textX = 14*queueFontSize, textY = rows + lineHeight; // REMOVE let currentTextX = 14 * queueFontSize; let currentNodeX = currentTextX + 1.5 * nodeRadius; let currentTextHeight = 1.5 * lineHeight; let nodeOffset = -3; let diagram = drawDijkstraDiagram(graph, state); let diagramY = currentTextHeight; let queueY = diagramY + rows + .75*lineHeight; let queueHeight = 4 * lineHeight; let queueX = 4.5 * queueFontSize; let queueNodeRadius = Math.min(nodeRadius, .667 * queueFontSize); let queueNodeLabelSize = 1.38 * queueNodeRadius; let queueNodeX = queueX + 2*queueNodeRadius; let queueNodeOffset = -1; let totalHeight = queueY + queueHeight; diagram = svg` `; return diagram; /* // hack for iPad, which shrinks it to nothing if we don't provide a width or height! ugh. diagram.style="min-width: 20em;" let body = ""; for (let {src,dst,dst_time} of state.queue) { body += `${dst_time}Reach ${dst.toUpperCase()}` } // TODO: instead of just time, a caption, e.g. "at time 2, fluid reaches node B from node A" // TODO: indicate which neighbors were just added to the queue w/ outline and hilight in table return html` time = ${state.time}

${diagram} ${body}

Event queue
Time	Event

` */ }35:T9cd,function drawDijkstraDiagram(graph, state) { let {time, visited_nodes, visited_edges, queue} = state; let node_svg = ``, edge_svg = ``, queue_svg = ``, label_svg = ``; // NODES for (let [name, v] of Object.entries(graph.nodes)) { let c = (name in visited_nodes) ? "visited" : ""; let a = name == state.node ? "active" : ""; if (state.neighbors.includes(name)) { //edge_svg += ``; //node_svg += ``; } node_svg += `\n`; if (true || name == state.node || state.queue.some(e => e.dst == name)) node_svg += `${name.toUpperCase()}\n`; } // EDGES & LABELS for (let {src,dst,length} of graph.edges) { let c = (visited_edges.some(([s,d]) => (s == src && d == dst) || (s == dst && d == src))) ? "visited" : ""; let v = graph.nodes[src], u = graph.nodes[dst]; edge_svg += `\n`; let lx = (v.x + u.x)/2, ly = (v.y+u.y)/2; let dx = v.x-u.x, dy = v.y-u.y; let distance = Math.sqrt(dx*dx+dy*dy); let ox = labelOffset*dy/distance, oy = -labelOffset*dx/distance; label_svg += `${length}\n`; } // QUEUE for (let {src,dst,src_time,dst_time} of queue) { // This avoids creating zero-length lines, which can ugly up the diagram. if (time == src_time) continue; let progress = (time - src_time)/(dst_time - src_time); let v = graph.nodes[src], u = graph.nodes[dst]; let dx = u.x-v.x, dy = u.y-v.y; // vector from v to u let distance = Math.sqrt(dx*dx + dy*dy); // we offset the start of the blue water by the node radius let vx = v.x + nodeRadius*dx/distance, vy = v.y + nodeRadius*dy/distance; let ux = u.x - nodeRadius*dx/distance, uy = u.y - nodeRadius*dy/distance; //ux = u.x; uy = u.y; let x2 = vx + progress * (ux-vx), y2 = vy + progress * (uy-vy); // console.log(src, dst, progress, v.x, x2, y2); queue_svg += `\n` } return svg` ${edge_svg} ${queue_svg} ${node_svg} ${label_svg} ` }36:Tc92,function draw(graph, state, options) { let {time, visited_nodes, visited_edges, queue, path_edges} = state; options = options === undefined ? [] : options.split(","); let node_svg = ``, edge_svg = ``, queue_svg = ``, label_svg = ``; // NODES for (let [name, v] of Object.entries(graph.nodes)) { let c = (name in visited_nodes) ? "visited" : ""; node_svg += `\n`; if (options.includes("distances") && name in state.visited_nodes && name != graph.start) { node_svg += `${state.visited_nodes[name]}\n`; } } // EDGES & LABELS for (let {src,dst,length} of graph.edges) { let c = (visited_edges.some(([s,d]) => (s == src && d == dst) || (s == dst && d == src))) ? ("visited" + (options.includes("paths") ? " longer" : "")) : ""; let v = graph.nodes[src], u = graph.nodes[dst]; edge_svg += `\n`; let lx = (v.x + u.x)/2, ly = (v.y+u.y)/2; let dx = v.x-u.x, dy = v.y-u.y; let distance = Math.sqrt(dx*dx+dy*dy); let ox = labelOffset*dy/distance, oy = -labelOffset*dx/distance; label_svg += `${length}\n`; let ok = (([s,d]) => (s == src && d == dst) || (s == dst && d == src)); if (options.includes("paths") && path_edges.some(ok)) { let [src,dst] = path_edges.find(ok); let v = graph.nodes[src], u = graph.nodes[dst]; let length = .88*nodeRadius; let dx = length*(u.x-v.x)/distance, dy = length*(u.y-v.y)/distance; let o = 1.414*strokeWidth; let ox= o*(v.y-u.y)/distance, oy = o*(u.x-v.x)/distance; let l = (length/2 + nodeRadius)/distance; let lx = u.x + l*(v.x-u.x), ly = u.y + l*(v.y-u.y); edge_svg += ` `; } } // QUEUE for (let {src,dst,src_time,dst_time} of queue) { // This avoids creating zero-length lines, which can ugly up the diagram. if (time == src_time) continue; let progress = (time - src_time)/(dst_time - src_time); let v = graph.nodes[src], u = graph.nodes[dst]; let dx = u.x-v.x, dy = u.y-v.y; // vector from v to u let distance = Math.sqrt(dx*dx + dy*dy); // we offset the start of the blue water by the node radius let vx = v.x + nodeRadius*dx/distance, vy = v.y + nodeRadius*dy/distance; let ux = u.x - nodeRadius*dx/distance, uy = u.y - nodeRadius*dy/distance; //ux = u.x; uy = u.y; let x2 = vx + progress * (ux-vx), y2 = vy + progress * (uy-vy); // console.log(src, dst, progress, v.x, x2, y2); queue_svg += `\n` } return svg`` }37:T86b,// Produces a list of states. A state is an object {time, visited_nodes, visited_edges, queue}. dijkstra_states = { let time = 0; // visited_nodes maps node names to the time they were reached let visited_nodes = {}; // list of visited edges, represented as two-element arrays [src,dst] let visited_edges = []; // a queue entry is {src, dst, src_time, dst_time} let queue = []; // Edges of shortest paths, oriented towards the source let path_edges = []; // a state is {time, node, visited_nodes, visited_edges, queue} let states = []; function reach(v) { visited_nodes[v] = time; let neighbors = []; for (let {src,dst,length} of graph.edges) { if (dst == v) [src,dst] = [dst,src]; if (src != v) continue; // In Dijkstra's we would normally avoid traversing edges to already-seen nodes, but when simulating fluid flow this is inappropriate. //if (visited_nodes.includes(dest)) continue; // Instead we avoid traversing edges we have already traversed in the opposite direction (such as the edge which brought us here). if (visited_edges.some(([s,d]) => s == dst && d == src)) continue; neighbors.push(dst); queue.push({src, dst, src_time: time, dst_time: time + length}) } // The world's worst priority queue implementation: sort after every batch of insertions queue.sort((a,b) => a.dst_time-b.dst_time); return neighbors } function visit(node) { let neighbors = []; if (!(node in visited_nodes)) neighbors = reach(node); states.push({ time, node, neighbors, path_edges: path_edges.slice(), visited_nodes: {...visited_nodes}, visited_edges: visited_edges.slice(), queue: queue.slice(), }) } visit(graph.start); // trick to avoid inflooping in case I make a mistake for (let i = 0; queue.length != 0 && i <= 2*graph.edges.length; i++) { let {dst_time, src, dst} = queue.shift(); time = dst_time; visited_edges.push([src,dst]); if (!(dst in visited_nodes)) path_edges.push([src,dst]); visit(dst); } if (queue.length != 0) { throw "oops" } return states }38:[] 31:{"id":"913a7613c5c41f0e","slug":"dijkstras","title":"A short explanation of Dijkstra’s shortest paths algorithm","thumbnail":null,"access_level":"public","create_time":"$D2021-08-10T22:42:31.995Z","update_time":"$D2021-10-05T12:56:54.603Z","view_time":null,"first_public_time":"$D2021-08-12T14:13:23.682Z","has_unpublished_edits":null,"fork":{"id":"b62f719d42128c80","slug":"breadth-first-search-demo","title":"Breadth first search demo","owner":{"id":"468ec444dc0eb0ae","login":"redblobgames","name":"Amit Patel"}},"stars":4,"starred":false,"owner":{"type":"team","id":"358dc3d73819e75d","login":"rntz","name":"Michael Arntzenius","avatar_url":"https://avatars-next.observableusercontent.com/92ecf6dc9a6973985a4f2faa401035fde2738e75da60019c475b4df8348c25dc","tier":"starter_2024"},"version":4396,"publish_version":4396,"role":null,"authored":false,"authors":[{"type":"individual","id":"55dae7d5ecb369c1","login":"rntz","name":"Michael Arntzenius","avatar_url":"https://avatars-next.observableusercontent.com/92ecf6dc9a6973985a4f2faa401035fde2738e75da60019c475b4df8348c25dc","tier":null}],"members":[{"type":"individual","id":"55dae7d5ecb369c1","login":"rntz","name":"Michael Arntzenius","avatar_url":"https://avatars-next.observableusercontent.com/92ecf6dc9a6973985a4f2faa401035fde2738e75da60019c475b4df8348c25dc","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":5,"collection":null,"type":"notebook","body":{"title":"A short explanation of Dijkstra’s shortest paths algorithm","cells":[{"id":2069,"value":"md`# A short explanation of Dijkstra’s shortest paths algorithm`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2078,"value":"md`\nDijkstra’s algorithm finds the shortest paths through a graph by simulating a fluid spreading through it at a constant speed.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2083,"value":"draw(graph, stateAt(Math.max(0, (now / 250) % (maxTime + 3) - 1)))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2086,"value":"md`\nBecause the fluid explores all paths simultaneously, it will reach a node soonest along the shortest path to it. So if we record *when* and *along which edge* the fluid first reaches each node, we will find the shortest paths and their lengths:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3904,"value":"draw(graph, stateAt(time1), \"paths,distances\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3901,"value":"viewof time1 = Inputs.range([0,maxTime], {label: \"Time\", step: 1, value: 0})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3891,"value":"md`\nBut how can we simulate this on a computer? If our edge-lengths are whole numbers, we can do so one step at a time, as shown above. But not all graphs are so conveniently fraction-free; and as our edges grow in length, a step-by-step simulation takes longer to complete. So instead, Dijkstra’s algorithm keeps an *event queue*. When a new node is reached ${newNodeReachedImage()}, we push its neighbors ${neighborsImage()} on the queue, ordered by the time the fluid will reach them along the connecting edge ${neighborEdgeImage()}. The next node reached is always the one on top of this time-sorted [priority queue](https://en.wikipedia.org/wiki/Priority_queue).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2091,"value":"viewof step0 = Inputs.range([0, dijkstraStatesPruned.length-1], \n {label: \"Step\", value: 0, step: 1})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2089,"value":"drawDijkstra(graph, dijkstraStatesPruned[step0])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4293,"value":"md`And that is the essence of Dijkstra's algorithm: simulate a fluid spreading through a graph at a constant speed, using a priority queue to visit nodes in the order the fluid reaches them. If you want to learn how priority queues work, you might try Wikipedia's articles on [priority queues](https://en.wikipedia.org/wiki/Priority_queue) and [heaps](https://en.wikipedia.org/wiki/Heap_%28data_structure%29). I also strongly recommend [redblobgames’ introduction to A*](https://www.redblobgames.com/pathfinding/a-star/introduction.html) for learning more about Dijkstra’s and its relative A\\\\*.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4149,"value":"html`fin`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2737,"value":"blackblock()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4255,"value":"md`# Implementation details`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4259,"value":"html`

Everything below this is an implementation detail which you may safely ignore.

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2442,"value":"newNodeReachedImage = () => svg``","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2534,"value":"neighborsImage = () => svg``","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2730,"value":"neighborEdgeImage = () => svg``","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1455,"value":"md`## Visualization`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":464,"value":"viewof step = Inputs.range([0, maxTime], {value: 0, step: 1, label: \"Time\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1487,"value":"draw(graph, currentState)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":796,"value":"viewof rows = Inputs.range([100,2000], {label: \"Rows\", step: 100, value: 400})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":797,"value":"viewof columns = Inputs.range([100,2000], {label: \"Columns\", step: 100, value: 800})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":740,"value":"viewof nodeRadius = Inputs.range([1,100], {value: 33, step: 1, label: \"Node radius\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":749,"value":"viewof strokeWidth = Inputs.range([1, 100], {value: 22, step: 1, label: \"Stroke width\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1158,"value":"viewof labelSize = Inputs.range([1,100], {label: \"Edge label size\", step: 1, value: strokeWidth*2})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2985,"value":"viewof nodeLabelSize = Inputs.range([1, 100], {label: \"Node label size\", step: 1, value: 38})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3250,"value":"viewof queueFontSize = Inputs.range([1,100], {label: \"Queue label size\", value: nodeLabelSize, step: 1})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3026,"value":"drawDijkstra(graph, currentState)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1916,"value":"//maxTime = dijkstra_states[dijkstra_states.length-1].time\nmaxTime = 10","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":593,"value":"currentState = stateAt(step)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":327,"value":"graph = myGraph","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1960,"value":"function scaleGraph(graph, scale) {\n return {...graph, edges: graph.edges.map(x => ({...x, length: x.length * scale})) }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":22,"value":"$33","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2110,"value":"$34","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2964,"value":"dijkstraStatesPruned = {\n //return dijkstra_states.filter(x => !x.alreadyReached);\n let states = [];\n for (let s of dijkstra_states) { states.push(s) }\n return states\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2979,"value":"$35","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":169,"value":"$36","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1229,"value":"labelOffset = strokeWidth + labelSize/2","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1981,"value":"blackblock = () => html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":517,"value":"md`## Graph`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":488,"value":"// node_strings = [\"a 1 1\", \"b 1 3\", \"c 3 1\", \"d 5 3\", \"e 5 1\", \"f 8 5\"]\nnode_strings = [\"a 0 0\", \"b 1 2\", \"c 3 0\", \"d 5 2\", \"e 6 0\"]","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":489,"value":"edge_strings = [\"a b 2\", \"c a 5\", \"b d 10\", \"c d 3\", \"b c 4\", \"d e 2\", \"e c 5\"]","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":313,"value":"myGraph = {\n let nodes = {};\n for (let n of node_strings) {\n let [name, x, y] = n.split(\" \");\n nodes[name] = {x: 100*(1+parseFloat(x)), y: 100*(1+parseFloat(y))};\n }\n let edges = [];\n for (let e of edge_strings) {\n let [src,dst,length] = e.split(\" \");\n edges.push({src, dst, length: parseInt(length)});\n }\n return {nodes, edges, start: \"a\"}\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":355,"value":"md`## Algorithm`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1483,"value":"emptyState = ({time: null, visited_nodes: {}, visited_edges: [], queue: []})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":568,"value":"// Produces {time, visited_nodes, visited_edges, queue}\nfunction stateAt(time) {\n const state = dijkstra_states.slice().reverse().find(x => x.time <= time);\n // Remarkably, the only thing we need to update is time; the only thing that changes in between dijkstra states is the progress of fluid along the edges in the queue, and that can be calculated from the current time and the source and destination times in the queue.\n return {...state, time};\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":60,"value":"$37","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1499,"value":"md`## Random Graph (unused)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":833,"value":"viewof numberNodes = Inputs.range([1,50], {label: \"Number of nodes\", step: 1, value: 10})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1506,"value":"viewof numberEdges = Inputs.range([1,50], {label: \"Number of edges\", step: 1, value: 10})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":783,"value":"randomGraph = {\n let nodes = {}, edges = [];\n for (let i = 0; i <= numberNodes; i++) {\n nodes[i] = {x: Math.floor(1 + Math.random() * (columns-1)), \n y: Math.floor(1 + Math.random() * (rows-1))}\n }\n for (let i = 0; i <= numberEdges; i++) {\n let j = Math.floor(numberNodes * Math.random());\n let k = Math.floor((numberNodes-1) * Math.random());\n if (j <= k) k++;\n edges.push({src: \"\"+j, dst: \"\"+k,\n length: 1 + Math.floor(Math.random() * 16)});\n }\n return {nodes, edges, start: \"0\"}\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W38","stdlib":"1","titling":"auto"}} 32:"$31:body"