{"algorithm":"dijkstra","about":["Dijkstra's algorithm gives the start a distance of 0 and every other vertex a distance of infinity, and keeps the vertices in a priority queue by distance. It takes the closest vertex out, which makes its distance final, and checks each edge from it. When the path through that vertex is shorter than a neighbor's current distance, the neighbor takes the shorter distance, and the edge it came by becomes its way in.","This works because no edge weight is negative. Once a vertex is the closest one left, no later path can reach it for less. With a negative edge that stops being true, and Bellman-Ford is the one to use. path.DijkstraPaths keeps one entry per vertex in a binary heap and moves it up when a shorter path turns up, so it costs O((V+E) log V). It goes on until every vertex it can reach is settled.","Distance and PathTo on its result give each distance and the route there, start first, and report false for a vertex the start can't reach, so there's no infinity to compare with. Of two routes that are equally short, it keeps the one it found first, and vertices at the same distance leave the queue in the order of the edges that reached them, so the same graph gives the same routes on every run.","path.Dijkstra returns the distances alone, with math.MaxFloat64 for a vertex it can't reach, and path.DijkstraSimple returns them with a plain list and a linear scan instead of a heap, in O(V²). The performance card on this page times all three on each example graph."],"template":{"id":"one-way-city","name":"One-way city","description":"Forty-five intersections, I1 to I45, where I stands for intersection, numbered row by row from the top left with nine to a row. Most streets are one way, and the outer streets form a clockwise loop. Only the middle row (I19 to I27) and the middle column (I5, I14, I23, I32 and I41) go both ways, and each edge is the travel time in minutes.","family":"road","directed":true,"weighted":true,"acyclic":false,"vertices":[{"id":"I1","x":64,"y":287},{"id":"I2","x":175,"y":279},{"id":"I3","x":288,"y":275},{"id":"I4","x":381,"y":280},{"id":"I5","x":500,"y":288},{"id":"I6","x":601,"y":274},{"id":"I7","x":715,"y":288},{"id":"I8","x":836,"y":273},{"id":"I9","x":947,"y":289},{"id":"I10","x":58,"y":382},{"id":"I11","x":177,"y":399},{"id":"I12","x":280,"y":398},{"id":"I13","x":395,"y":389},{"id":"I14","x":492,"y":379},{"id":"I15","x":614,"y":383},{"id":"I16","x":720,"y":392},{"id":"I17","x":833,"y":382},{"id":"I18","x":942,"y":384},{"id":"I19","x":55,"y":502},{"id":"I20","x":168,"y":497},{"id":"I21","x":282,"y":490},{"id":"I22","x":393,"y":509},{"id":"I23","x":499,"y":491},{"id":"I24","x":613,"y":508},{"id":"I25","x":714,"y":501},{"id":"I26","x":820,"y":492},{"id":"I27","x":937,"y":502},{"id":"I28","x":67,"y":610},{"id":"I29","x":171,"y":617},{"id":"I30","x":288,"y":600},{"id":"I31","x":392,"y":611},{"id":"I32","x":510,"y":613},{"id":"I33","x":605,"y":600},{"id":"I34","x":725,"y":611},{"id":"I35","x":839,"y":607},{"id":"I36","x":938,"y":605},{"id":"I37","x":56,"y":719},{"id":"I38","x":171,"y":722},{"id":"I39","x":283,"y":728},{"id":"I40","x":391,"y":711},{"id":"I41","x":510,"y":716},{"id":"I42","x":613,"y":724},{"id":"I43","x":715,"y":719},{"id":"I44","x":838,"y":712},{"id":"I45","x":943,"y":720}],"edges":[{"from":"I1","to":"I2","weight":3},{"from":"I10","to":"I1","weight":5},{"from":"I2","to":"I3","weight":2},{"from":"I2","to":"I11","weight":4},{"from":"I3","to":"I4","weight":3},{"from":"I12","to":"I3","weight":4},{"from":"I4","to":"I5","weight":2},{"from":"I4","to":"I13","weight":2},{"from":"I5","to":"I6","weight":5},{"from":"I5","to":"I14","weight":5},{"from":"I14","to":"I5","weight":5},{"from":"I6","to":"I7","weight":4},{"from":"I15","to":"I6","weight":4},{"from":"I7","to":"I8","weight":4},{"from":"I7","to":"I16","weight":3},{"from":"I8","to":"I9","weight":4},{"from":"I17","to":"I8","weight":5},{"from":"I9","to":"I18","weight":2},{"from":"I11","to":"I10","weight":4},{"from":"I19","to":"I10","weight":5},{"from":"I12","to":"I11","weight":5},{"from":"I11","to":"I20","weight":3},{"from":"I13","to":"I12","weight":5},{"from":"I21","to":"I12","weight":2},{"from":"I14","to":"I13","weight":4},{"from":"I13","to":"I22","weight":3},{"from":"I15","to":"I14","weight":2},{"from":"I14","to":"I23","weight":3},{"from":"I23","to":"I14","weight":3},{"from":"I16","to":"I15","weight":2},{"from":"I24","to":"I15","weight":4},{"from":"I17","to":"I16","weight":2},{"from":"I16","to":"I25","weight":2},{"from":"I18","to":"I17","weight":4},{"from":"I26","to":"I17","weight":4},{"from":"I18","to":"I27","weight":5},{"from":"I19","to":"I20","weight":3},{"from":"I20","to":"I19","weight":3},{"from":"I28","to":"I19","weight":4},{"from":"I20","to":"I21","weight":2},{"from":"I21","to":"I20","weight":2},{"from":"I20","to":"I29","weight":3},{"from":"I21","to":"I22","weight":3},{"from":"I22","to":"I21","weight":3},{"from":"I30","to":"I21","weight":3},{"from":"I22","to":"I23","weight":5},{"from":"I23","to":"I22","weight":5},{"from":"I22","to":"I31","weight":2},{"from":"I23","to":"I24","weight":5},{"from":"I24","to":"I23","weight":5},{"from":"I23","to":"I32","weight":5},{"from":"I32","to":"I23","weight":5},{"from":"I24","to":"I25","weight":2},{"from":"I25","to":"I24","weight":2},{"from":"I33","to":"I24","weight":2},{"from":"I25","to":"I26","weight":4},{"from":"I26","to":"I25","weight":4},{"from":"I25","to":"I34","weight":3},{"from":"I26","to":"I27","weight":5},{"from":"I27","to":"I26","weight":5},{"from":"I35","to":"I26","weight":5},{"from":"I27","to":"I36","weight":3},{"from":"I28","to":"I29","weight":3},{"from":"I37","to":"I28","weight":4},{"from":"I29","to":"I30","weight":2},{"from":"I29","to":"I38","weight":4},{"from":"I30","to":"I31","weight":4},{"from":"I39","to":"I30","weight":3},{"from":"I31","to":"I32","weight":5},{"from":"I31","to":"I40","weight":3},{"from":"I32","to":"I33","weight":5},{"from":"I32","to":"I41","weight":4},{"from":"I41","to":"I32","weight":4},{"from":"I33","to":"I34","weight":3},{"from":"I42","to":"I33","weight":2},{"from":"I34","to":"I35","weight":5},{"from":"I34","to":"I43","weight":3},{"from":"I35","to":"I36","weight":5},{"from":"I44","to":"I35","weight":2},{"from":"I36","to":"I45","weight":2},{"from":"I38","to":"I37","weight":3},{"from":"I39","to":"I38","weight":2},{"from":"I40","to":"I39","weight":2},{"from":"I41","to":"I40","weight":2},{"from":"I42","to":"I41","weight":2},{"from":"I43","to":"I42","weight":3},{"from":"I44","to":"I43","weight":5},{"from":"I45","to":"I44","weight":3}],"details":{"vertices":45,"edges":88,"directed":true,"weighted":true,"acyclic":false,"weightMin":2,"weightMax":5,"negativeWeights":false,"density":0.044444444444444446,"inDegree":{"min":1,"avg":1.9555555555555555,"max":4},"outDegree":{"min":1,"avg":1.9555555555555555,"max":4},"selfLoops":0,"components":1}},"problem":"How many minutes is the quickest drive from I23 to each intersection, when most streets are one way?","params":{"start":"I23"},"result":{"kind":"distances","values":{"I1":23,"I10":18,"I11":15,"I12":10,"I13":7,"I14":3,"I15":9,"I16":17,"I17":15,"I18":26,"I19":13,"I2":26,"I20":10,"I21":8,"I22":5,"I23":0,"I24":5,"I25":7,"I26":11,"I27":16,"I28":21,"I29":13,"I3":14,"I30":15,"I31":7,"I32":5,"I33":10,"I34":10,"I35":15,"I36":19,"I37":17,"I38":14,"I39":12,"I4":17,"I40":10,"I41":9,"I42":16,"I43":13,"I44":24,"I45":21,"I5":8,"I6":13,"I7":17,"I8":20,"I9":24}},"answer":"From I23, the shortest distances are 3 to I14, 5 to I22, 5 to I24, 5 to I32, 7 to I13, 7 to I25, 7 to I31, 8 to I5, 8 to I21, 9 to I15 and 34 more. The farthest is I18, at 26.","legend":{"vertex":[{"id":"idle","label":"Not reached","color":"#64748B","shape":"hollow"},{"id":"waiting","label":"In queue","color":"#E69F00","shape":"dashed-square"},{"id":"current","label":"Being settled","color":"#56B4E9","shape":"ring"},{"id":"done","label":"Settled","color":"#009E73","shape":"filled"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"tree","label":"On a shortest path","color":"#009E73","shape":"thick"},{"id":"examined","label":"Checked, not shorter","color":"#CC79A7","shape":"dashed"}],"panels":[{"id":"queue","title":"Priority queue","kind":"list"},{"id":"dist","title":"Distances","kind":"table"}]},"steps":[{"say":"Every distance starts at ∞, except I23, which is 0. Put I23 in the queue.","ops":[{"v":"I23","state":"waiting"},{"panel":"dist","set":{"I1":"∞"}},{"panel":"dist","set":{"I2":"∞"}},{"panel":"dist","set":{"I3":"∞"}},{"panel":"dist","set":{"I4":"∞"}},{"panel":"dist","set":{"I5":"∞"}},{"panel":"dist","set":{"I6":"∞"}},{"panel":"dist","set":{"I7":"∞"}},{"panel":"dist","set":{"I8":"∞"}},{"panel":"dist","set":{"I9":"∞"}},{"panel":"dist","set":{"I10":"∞"}},{"panel":"dist","set":{"I11":"∞"}},{"panel":"dist","set":{"I12":"∞"}},{"panel":"dist","set":{"I13":"∞"}},{"panel":"dist","set":{"I14":"∞"}},{"panel":"dist","set":{"I15":"∞"}},{"panel":"dist","set":{"I16":"∞"}},{"panel":"dist","set":{"I17":"∞"}},{"panel":"dist","set":{"I18":"∞"}},{"panel":"dist","set":{"I19":"∞"}},{"panel":"dist","set":{"I20":"∞"}},{"panel":"dist","set":{"I21":"∞"}},{"panel":"dist","set":{"I22":"∞"}},{"panel":"dist","set":{"I23":"0"}},{"panel":"dist","set":{"I24":"∞"}},{"panel":"dist","set":{"I25":"∞"}},{"panel":"dist","set":{"I26":"∞"}},{"panel":"dist","set":{"I27":"∞"}},{"panel":"dist","set":{"I28":"∞"}},{"panel":"dist","set":{"I29":"∞"}},{"panel":"dist","set":{"I30":"∞"}},{"panel":"dist","set":{"I31":"∞"}},{"panel":"dist","set":{"I32":"∞"}},{"panel":"dist","set":{"I33":"∞"}},{"panel":"dist","set":{"I34":"∞"}},{"panel":"dist","set":{"I35":"∞"}},{"panel":"dist","set":{"I36":"∞"}},{"panel":"dist","set":{"I37":"∞"}},{"panel":"dist","set":{"I38":"∞"}},{"panel":"dist","set":{"I39":"∞"}},{"panel":"dist","set":{"I40":"∞"}},{"panel":"dist","set":{"I41":"∞"}},{"panel":"dist","set":{"I42":"∞"}},{"panel":"dist","set":{"I43":"∞"}},{"panel":"dist","set":{"I44":"∞"}},{"panel":"dist","set":{"I45":"∞"}},{"panel":"queue","list":[{"key":"I23","note":"0"}]}]},{"say":"Take I23 from the queue. Its distance, 0, is now final.","ops":[{"v":"I23","state":"current"},{"panel":"queue","list":[]}]},{"say":"I23 to I14: 0 + 3 = 3, so I14's distance becomes 3. Put I14 in the queue.","ops":[{"v":"I14","state":"waiting"},{"e":["I23","I14"],"state":"tree"},{"panel":"dist","set":{"I14":"3"}},{"panel":"queue","list":[{"key":"I14","note":"3"}]}]},{"say":"I23 to I22: 0 + 5 = 5, so I22's distance becomes 5. Put I22 in the queue.","ops":[{"v":"I22","state":"waiting"},{"e":["I23","I22"],"state":"tree"},{"panel":"dist","set":{"I22":"5"}},{"panel":"queue","list":[{"key":"I14","note":"3"},{"key":"I22","note":"5"}]}]},{"say":"I23 to I24: 0 + 5 = 5, so I24's distance becomes 5. Put I24 in the queue.","ops":[{"v":"I24","state":"waiting"},{"e":["I23","I24"],"state":"tree"},{"panel":"dist","set":{"I24":"5"}},{"panel":"queue","list":[{"key":"I14","note":"3"},{"key":"I22","note":"5"},{"key":"I24","note":"5"}]}]},{"say":"I23 to I32: 0 + 5 = 5, so I32's distance becomes 5. Put I32 in the queue.","ops":[{"v":"I32","state":"waiting"},{"e":["I23","I32"],"state":"tree"},{"panel":"dist","set":{"I32":"5"}},{"panel":"queue","list":[{"key":"I14","note":"3"},{"key":"I22","note":"5"},{"key":"I24","note":"5"},{"key":"I32","note":"5"}]}]},{"say":"Take I14 from the queue. Its distance, 3, is now final.","ops":[{"v":"I14","state":"current"},{"panel":"queue","list":[{"key":"I22","note":"5"},{"key":"I24","note":"5"},{"key":"I32","note":"5"}]},{"v":"I23","state":"done"}]},{"say":"I14 to I5: 3 + 5 = 8, so I5's distance becomes 8. Put I5 in the queue.","ops":[{"v":"I5","state":"waiting"},{"e":["I14","I5"],"state":"tree"},{"panel":"dist","set":{"I5":"8"}},{"panel":"queue","list":[{"key":"I22","note":"5"},{"key":"I24","note":"5"},{"key":"I32","note":"5"},{"key":"I5","note":"8"}]}]},{"say":"I14 to I13: 3 + 4 = 7, so I13's distance becomes 7. Put I13 in the queue.","ops":[{"v":"I13","state":"waiting"},{"e":["I14","I13"],"state":"tree"},{"panel":"dist","set":{"I13":"7"}},{"panel":"queue","list":[{"key":"I22","note":"5"},{"key":"I24","note":"5"},{"key":"I32","note":"5"},{"key":"I13","note":"7"},{"key":"I5","note":"8"}]}]},{"say":"Take I22 from the queue. Its distance, 5, is now final.","ops":[{"v":"I22","state":"current"},{"panel":"queue","list":[{"key":"I24","note":"5"},{"key":"I32","note":"5"},{"key":"I13","note":"7"},{"key":"I5","note":"8"}]},{"v":"I14","state":"done"}]},{"say":"I22 to I21: 5 + 3 = 8, so I21's distance becomes 8. Put I21 in the queue.","ops":[{"v":"I21","state":"waiting"},{"e":["I22","I21"],"state":"tree"},{"panel":"dist","set":{"I21":"8"}},{"panel":"queue","list":[{"key":"I24","note":"5"},{"key":"I32","note":"5"},{"key":"I13","note":"7"},{"key":"I5","note":"8"},{"key":"I21","note":"8"}]}]},{"say":"I22 to I31: 5 + 2 = 7, so I31's distance becomes 7. Put I31 in the queue.","ops":[{"v":"I31","state":"waiting"},{"e":["I22","I31"],"state":"tree"},{"panel":"dist","set":{"I31":"7"}},{"panel":"queue","list":[{"key":"I24","note":"5"},{"key":"I32","note":"5"},{"key":"I13","note":"7"},{"key":"I31","note":"7"},{"key":"I5","note":"8"},{"key":"I21","note":"8"}]}]},{"say":"Take I24 from the queue. Its distance, 5, is now final.","ops":[{"v":"I24","state":"current"},{"panel":"queue","list":[{"key":"I32","note":"5"},{"key":"I13","note":"7"},{"key":"I31","note":"7"},{"key":"I5","note":"8"},{"key":"I21","note":"8"}]},{"v":"I22","state":"done"}]},{"say":"I24 to I15: 5 + 4 = 9, so I15's distance becomes 9. Put I15 in the queue.","ops":[{"v":"I15","state":"waiting"},{"e":["I24","I15"],"state":"tree"},{"panel":"dist","set":{"I15":"9"}},{"panel":"queue","list":[{"key":"I32","note":"5"},{"key":"I13","note":"7"},{"key":"I31","note":"7"},{"key":"I5","note":"8"},{"key":"I21","note":"8"},{"key":"I15","note":"9"}]}]},{"say":"I24 to I25: 5 + 2 = 7, so I25's distance becomes 7. Put I25 in the queue.","ops":[{"v":"I25","state":"waiting"},{"e":["I24","I25"],"state":"tree"},{"panel":"dist","set":{"I25":"7"}},{"panel":"queue","list":[{"key":"I32","note":"5"},{"key":"I13","note":"7"},{"key":"I31","note":"7"},{"key":"I25","note":"7"},{"key":"I5","note":"8"},{"key":"I21","note":"8"},{"key":"I15","note":"9"}]}]},{"say":"Take I32 from the queue. Its distance, 5, is now final.","ops":[{"v":"I32","state":"current"},{"panel":"queue","list":[{"key":"I13","note":"7"},{"key":"I31","note":"7"},{"key":"I25","note":"7"},{"key":"I5","note":"8"},{"key":"I21","note":"8"},{"key":"I15","note":"9"}]},{"v":"I24","state":"done"}]},{"say":"I32 to I33: 5 + 5 = 10, so I33's distance becomes 10. Put I33 in the queue.","ops":[{"v":"I33","state":"waiting"},{"e":["I32","I33"],"state":"tree"},{"panel":"dist","set":{"I33":"10"}},{"panel":"queue","list":[{"key":"I13","note":"7"},{"key":"I31","note":"7"},{"key":"I25","note":"7"},{"key":"I5","note":"8"},{"key":"I21","note":"8"},{"key":"I15","note":"9"},{"key":"I33","note":"10"}]}]},{"say":"I32 to I41: 5 + 4 = 9, so I41's distance becomes 9. Put I41 in the queue.","ops":[{"v":"I41","state":"waiting"},{"e":["I32","I41"],"state":"tree"},{"panel":"dist","set":{"I41":"9"}},{"panel":"queue","list":[{"key":"I13","note":"7"},{"key":"I31","note":"7"},{"key":"I25","note":"7"},{"key":"I5","note":"8"},{"key":"I21","note":"8"},{"key":"I15","note":"9"},{"key":"I41","note":"9"},{"key":"I33","note":"10"}]}]},{"say":"Take I13 from the queue. Its distance, 7, is now final.","ops":[{"v":"I13","state":"current"},{"panel":"queue","list":[{"key":"I31","note":"7"},{"key":"I25","note":"7"},{"key":"I5","note":"8"},{"key":"I21","note":"8"},{"key":"I15","note":"9"},{"key":"I41","note":"9"},{"key":"I33","note":"10"}]},{"v":"I32","state":"done"}]},{"say":"I13 to I12: 7 + 5 = 12, so I12's distance becomes 12. Put I12 in the queue.","ops":[{"v":"I12","state":"waiting"},{"e":["I13","I12"],"state":"tree"},{"panel":"dist","set":{"I12":"12"}},{"panel":"queue","list":[{"key":"I31","note":"7"},{"key":"I25","note":"7"},{"key":"I5","note":"8"},{"key":"I21","note":"8"},{"key":"I15","note":"9"},{"key":"I41","note":"9"},{"key":"I33","note":"10"},{"key":"I12","note":"12"}]}]},{"say":"Take I31 from the queue. Its distance, 7, is now final.","ops":[{"v":"I31","state":"current"},{"panel":"queue","list":[{"key":"I25","note":"7"},{"key":"I5","note":"8"},{"key":"I21","note":"8"},{"key":"I15","note":"9"},{"key":"I41","note":"9"},{"key":"I33","note":"10"},{"key":"I12","note":"12"}]},{"v":"I13","state":"done"}]},{"say":"I31 to I40: 7 + 3 = 10, so I40's distance becomes 10. Put I40 in the queue.","ops":[{"v":"I40","state":"waiting"},{"e":["I31","I40"],"state":"tree"},{"panel":"dist","set":{"I40":"10"}},{"panel":"queue","list":[{"key":"I25","note":"7"},{"key":"I5","note":"8"},{"key":"I21","note":"8"},{"key":"I15","note":"9"},{"key":"I41","note":"9"},{"key":"I40","note":"10"},{"key":"I33","note":"10"},{"key":"I12","note":"12"}]}]},{"say":"Take I25 from the queue. Its distance, 7, is now final.","ops":[{"v":"I25","state":"current"},{"panel":"queue","list":[{"key":"I5","note":"8"},{"key":"I21","note":"8"},{"key":"I15","note":"9"},{"key":"I41","note":"9"},{"key":"I40","note":"10"},{"key":"I33","note":"10"},{"key":"I12","note":"12"}]},{"v":"I31","state":"done"}]},{"say":"I25 to I26: 7 + 4 = 11, so I26's distance becomes 11. Put I26 in the queue.","ops":[{"v":"I26","state":"waiting"},{"e":["I25","I26"],"state":"tree"},{"panel":"dist","set":{"I26":"11"}},{"panel":"queue","list":[{"key":"I5","note":"8"},{"key":"I21","note":"8"},{"key":"I15","note":"9"},{"key":"I41","note":"9"},{"key":"I40","note":"10"},{"key":"I33","note":"10"},{"key":"I26","note":"11"},{"key":"I12","note":"12"}]}]},{"say":"I25 to I34: 7 + 3 = 10, so I34's distance becomes 10. Put I34 in the queue.","ops":[{"v":"I34","state":"waiting"},{"e":["I25","I34"],"state":"tree"},{"panel":"dist","set":{"I34":"10"}},{"panel":"queue","list":[{"key":"I5","note":"8"},{"key":"I21","note":"8"},{"key":"I15","note":"9"},{"key":"I41","note":"9"},{"key":"I34","note":"10"},{"key":"I40","note":"10"},{"key":"I33","note":"10"},{"key":"I26","note":"11"},{"key":"I12","note":"12"}]}]},{"say":"Take I5 from the queue. Its distance, 8, is now final.","ops":[{"v":"I5","state":"current"},{"panel":"queue","list":[{"key":"I21","note":"8"},{"key":"I15","note":"9"},{"key":"I41","note":"9"},{"key":"I34","note":"10"},{"key":"I40","note":"10"},{"key":"I33","note":"10"},{"key":"I26","note":"11"},{"key":"I12","note":"12"}]},{"v":"I25","state":"done"}]},{"say":"I5 to I6: 8 + 5 = 13, so I6's distance becomes 13. Put I6 in the queue.","ops":[{"v":"I6","state":"waiting"},{"e":["I5","I6"],"state":"tree"},{"panel":"dist","set":{"I6":"13"}},{"panel":"queue","list":[{"key":"I21","note":"8"},{"key":"I15","note":"9"},{"key":"I41","note":"9"},{"key":"I34","note":"10"},{"key":"I40","note":"10"},{"key":"I33","note":"10"},{"key":"I26","note":"11"},{"key":"I12","note":"12"},{"key":"I6","note":"13"}]}]},{"say":"Take I21 from the queue. Its distance, 8, is now final.","ops":[{"v":"I21","state":"current"},{"panel":"queue","list":[{"key":"I15","note":"9"},{"key":"I41","note":"9"},{"key":"I34","note":"10"},{"key":"I40","note":"10"},{"key":"I33","note":"10"},{"key":"I26","note":"11"},{"key":"I12","note":"12"},{"key":"I6","note":"13"}]},{"v":"I5","state":"done"}]},{"say":"I21 to I12: 8 + 2 = 10, shorter than 12, so I12's distance becomes 10. Move I12 up the queue.","ops":[{"e":["I21","I12"],"state":"tree"},{"e":["I13","I12"],"state":"examined"},{"panel":"dist","set":{"I12":"10"}},{"panel":"queue","list":[{"key":"I15","note":"9"},{"key":"I41","note":"9"},{"key":"I12","note":"10"},{"key":"I34","note":"10"},{"key":"I40","note":"10"},{"key":"I33","note":"10"},{"key":"I26","note":"11"},{"key":"I6","note":"13"}]}]},{"say":"I21 to I20: 8 + 2 = 10, so I20's distance becomes 10. Put I20 in the queue.","ops":[{"v":"I20","state":"waiting"},{"e":["I21","I20"],"state":"tree"},{"panel":"dist","set":{"I20":"10"}},{"panel":"queue","list":[{"key":"I15","note":"9"},{"key":"I41","note":"9"},{"key":"I12","note":"10"},{"key":"I20","note":"10"},{"key":"I34","note":"10"},{"key":"I40","note":"10"},{"key":"I33","note":"10"},{"key":"I26","note":"11"},{"key":"I6","note":"13"}]}]},{"say":"Take I15 from the queue. Its distance, 9, is now final.","ops":[{"v":"I15","state":"current"},{"panel":"queue","list":[{"key":"I41","note":"9"},{"key":"I12","note":"10"},{"key":"I20","note":"10"},{"key":"I34","note":"10"},{"key":"I40","note":"10"},{"key":"I33","note":"10"},{"key":"I26","note":"11"},{"key":"I6","note":"13"}]},{"v":"I21","state":"done"}]},{"say":"I15 to I6: 9 + 4 = 13, not shorter than 13, so I6 keeps 13.","ops":[{"e":["I15","I6"],"state":"examined"}]},{"say":"Take I41 from the queue. Its distance, 9, is now final.","ops":[{"v":"I41","state":"current"},{"panel":"queue","list":[{"key":"I12","note":"10"},{"key":"I20","note":"10"},{"key":"I34","note":"10"},{"key":"I40","note":"10"},{"key":"I33","note":"10"},{"key":"I26","note":"11"},{"key":"I6","note":"13"}]},{"v":"I15","state":"done"}]},{"say":"I41 to I40: 9 + 2 = 11, not shorter than 10, so I40 keeps 10.","ops":[{"e":["I41","I40"],"state":"examined"}]},{"say":"Take I12 from the queue. Its distance, 10, is now final.","ops":[{"v":"I12","state":"current"},{"panel":"queue","list":[{"key":"I20","note":"10"},{"key":"I34","note":"10"},{"key":"I40","note":"10"},{"key":"I33","note":"10"},{"key":"I26","note":"11"},{"key":"I6","note":"13"}]},{"v":"I41","state":"done"}]},{"say":"I12 to I3: 10 + 4 = 14, so I3's distance becomes 14. Put I3 in the queue.","ops":[{"v":"I3","state":"waiting"},{"e":["I12","I3"],"state":"tree"},{"panel":"dist","set":{"I3":"14"}},{"panel":"queue","list":[{"key":"I20","note":"10"},{"key":"I34","note":"10"},{"key":"I40","note":"10"},{"key":"I33","note":"10"},{"key":"I26","note":"11"},{"key":"I6","note":"13"},{"key":"I3","note":"14"}]}]},{"say":"I12 to I11: 10 + 5 = 15, so I11's distance becomes 15. Put I11 in the queue.","ops":[{"v":"I11","state":"waiting"},{"e":["I12","I11"],"state":"tree"},{"panel":"dist","set":{"I11":"15"}},{"panel":"queue","list":[{"key":"I20","note":"10"},{"key":"I34","note":"10"},{"key":"I40","note":"10"},{"key":"I33","note":"10"},{"key":"I26","note":"11"},{"key":"I6","note":"13"},{"key":"I3","note":"14"},{"key":"I11","note":"15"}]}]},{"say":"Take I20 from the queue. Its distance, 10, is now final.","ops":[{"v":"I20","state":"current"},{"panel":"queue","list":[{"key":"I34","note":"10"},{"key":"I40","note":"10"},{"key":"I33","note":"10"},{"key":"I26","note":"11"},{"key":"I6","note":"13"},{"key":"I3","note":"14"},{"key":"I11","note":"15"}]},{"v":"I12","state":"done"}]},{"say":"I20 to I19: 10 + 3 = 13, so I19's distance becomes 13. Put I19 in the queue.","ops":[{"v":"I19","state":"waiting"},{"e":["I20","I19"],"state":"tree"},{"panel":"dist","set":{"I19":"13"}},{"panel":"queue","list":[{"key":"I34","note":"10"},{"key":"I40","note":"10"},{"key":"I33","note":"10"},{"key":"I26","note":"11"},{"key":"I6","note":"13"},{"key":"I19","note":"13"},{"key":"I3","note":"14"},{"key":"I11","note":"15"}]}]},{"say":"I20 to I29: 10 + 3 = 13, so I29's distance becomes 13. Put I29 in the queue.","ops":[{"v":"I29","state":"waiting"},{"e":["I20","I29"],"state":"tree"},{"panel":"dist","set":{"I29":"13"}},{"panel":"queue","list":[{"key":"I34","note":"10"},{"key":"I40","note":"10"},{"key":"I33","note":"10"},{"key":"I26","note":"11"},{"key":"I6","note":"13"},{"key":"I19","note":"13"},{"key":"I29","note":"13"},{"key":"I3","note":"14"},{"key":"I11","note":"15"}]}]},{"say":"Take I34 from the queue. Its distance, 10, is now final.","ops":[{"v":"I34","state":"current"},{"panel":"queue","list":[{"key":"I40","note":"10"},{"key":"I33","note":"10"},{"key":"I26","note":"11"},{"key":"I6","note":"13"},{"key":"I19","note":"13"},{"key":"I29","note":"13"},{"key":"I3","note":"14"},{"key":"I11","note":"15"}]},{"v":"I20","state":"done"}]},{"say":"I34 to I35: 10 + 5 = 15, so I35's distance becomes 15. Put I35 in the queue.","ops":[{"v":"I35","state":"waiting"},{"e":["I34","I35"],"state":"tree"},{"panel":"dist","set":{"I35":"15"}},{"panel":"queue","list":[{"key":"I40","note":"10"},{"key":"I33","note":"10"},{"key":"I26","note":"11"},{"key":"I6","note":"13"},{"key":"I19","note":"13"},{"key":"I29","note":"13"},{"key":"I3","note":"14"},{"key":"I11","note":"15"},{"key":"I35","note":"15"}]}]},{"say":"I34 to I43: 10 + 3 = 13, so I43's distance becomes 13. Put I43 in the queue.","ops":[{"v":"I43","state":"waiting"},{"e":["I34","I43"],"state":"tree"},{"panel":"dist","set":{"I43":"13"}},{"panel":"queue","list":[{"key":"I40","note":"10"},{"key":"I33","note":"10"},{"key":"I26","note":"11"},{"key":"I6","note":"13"},{"key":"I19","note":"13"},{"key":"I29","note":"13"},{"key":"I43","note":"13"},{"key":"I3","note":"14"},{"key":"I11","note":"15"},{"key":"I35","note":"15"}]}]},{"say":"Take I40 from the queue. Its distance, 10, is now final.","ops":[{"v":"I40","state":"current"},{"panel":"queue","list":[{"key":"I33","note":"10"},{"key":"I26","note":"11"},{"key":"I6","note":"13"},{"key":"I19","note":"13"},{"key":"I29","note":"13"},{"key":"I43","note":"13"},{"key":"I3","note":"14"},{"key":"I11","note":"15"},{"key":"I35","note":"15"}]},{"v":"I34","state":"done"}]},{"say":"I40 to I39: 10 + 2 = 12, so I39's distance becomes 12. Put I39 in the queue.","ops":[{"v":"I39","state":"waiting"},{"e":["I40","I39"],"state":"tree"},{"panel":"dist","set":{"I39":"12"}},{"panel":"queue","list":[{"key":"I33","note":"10"},{"key":"I26","note":"11"},{"key":"I39","note":"12"},{"key":"I6","note":"13"},{"key":"I19","note":"13"},{"key":"I29","note":"13"},{"key":"I43","note":"13"},{"key":"I3","note":"14"},{"key":"I11","note":"15"},{"key":"I35","note":"15"}]}]},{"say":"Take I33 from the queue. Its distance, 10, is now final. It has no unsettled neighbors.","ops":[{"v":"I33","state":"current"},{"panel":"queue","list":[{"key":"I26","note":"11"},{"key":"I39","note":"12"},{"key":"I6","note":"13"},{"key":"I19","note":"13"},{"key":"I29","note":"13"},{"key":"I43","note":"13"},{"key":"I3","note":"14"},{"key":"I11","note":"15"},{"key":"I35","note":"15"}]},{"v":"I40","state":"done"}]},{"say":"Take I26 from the queue. Its distance, 11, is now final.","ops":[{"v":"I26","state":"current"},{"panel":"queue","list":[{"key":"I39","note":"12"},{"key":"I6","note":"13"},{"key":"I19","note":"13"},{"key":"I29","note":"13"},{"key":"I43","note":"13"},{"key":"I3","note":"14"},{"key":"I11","note":"15"},{"key":"I35","note":"15"}]},{"v":"I33","state":"done"}]},{"say":"I26 to I17: 11 + 4 = 15, so I17's distance becomes 15. Put I17 in the queue.","ops":[{"v":"I17","state":"waiting"},{"e":["I26","I17"],"state":"tree"},{"panel":"dist","set":{"I17":"15"}},{"panel":"queue","list":[{"key":"I39","note":"12"},{"key":"I6","note":"13"},{"key":"I19","note":"13"},{"key":"I29","note":"13"},{"key":"I43","note":"13"},{"key":"I3","note":"14"},{"key":"I11","note":"15"},{"key":"I17","note":"15"},{"key":"I35","note":"15"}]}]},{"say":"I26 to I27: 11 + 5 = 16, so I27's distance becomes 16. Put I27 in the queue.","ops":[{"v":"I27","state":"waiting"},{"e":["I26","I27"],"state":"tree"},{"panel":"dist","set":{"I27":"16"}},{"panel":"queue","list":[{"key":"I39","note":"12"},{"key":"I6","note":"13"},{"key":"I19","note":"13"},{"key":"I29","note":"13"},{"key":"I43","note":"13"},{"key":"I3","note":"14"},{"key":"I11","note":"15"},{"key":"I17","note":"15"},{"key":"I35","note":"15"},{"key":"I27","note":"16"}]}]},{"say":"Take I39 from the queue. Its distance, 12, is now final.","ops":[{"v":"I39","state":"current"},{"panel":"queue","list":[{"key":"I6","note":"13"},{"key":"I19","note":"13"},{"key":"I29","note":"13"},{"key":"I43","note":"13"},{"key":"I3","note":"14"},{"key":"I11","note":"15"},{"key":"I17","note":"15"},{"key":"I35","note":"15"},{"key":"I27","note":"16"}]},{"v":"I26","state":"done"}]},{"say":"I39 to I30: 12 + 3 = 15, so I30's distance becomes 15. Put I30 in the queue.","ops":[{"v":"I30","state":"waiting"},{"e":["I39","I30"],"state":"tree"},{"panel":"dist","set":{"I30":"15"}},{"panel":"queue","list":[{"key":"I6","note":"13"},{"key":"I19","note":"13"},{"key":"I29","note":"13"},{"key":"I43","note":"13"},{"key":"I3","note":"14"},{"key":"I11","note":"15"},{"key":"I17","note":"15"},{"key":"I30","note":"15"},{"key":"I35","note":"15"},{"key":"I27","note":"16"}]}]},{"say":"I39 to I38: 12 + 2 = 14, so I38's distance becomes 14. Put I38 in the queue.","ops":[{"v":"I38","state":"waiting"},{"e":["I39","I38"],"state":"tree"},{"panel":"dist","set":{"I38":"14"}},{"panel":"queue","list":[{"key":"I6","note":"13"},{"key":"I19","note":"13"},{"key":"I29","note":"13"},{"key":"I43","note":"13"},{"key":"I3","note":"14"},{"key":"I38","note":"14"},{"key":"I11","note":"15"},{"key":"I17","note":"15"},{"key":"I30","note":"15"},{"key":"I35","note":"15"},{"key":"I27","note":"16"}]}]},{"say":"Take I6 from the queue. Its distance, 13, is now final.","ops":[{"v":"I6","state":"current"},{"panel":"queue","list":[{"key":"I19","note":"13"},{"key":"I29","note":"13"},{"key":"I43","note":"13"},{"key":"I3","note":"14"},{"key":"I38","note":"14"},{"key":"I11","note":"15"},{"key":"I17","note":"15"},{"key":"I30","note":"15"},{"key":"I35","note":"15"},{"key":"I27","note":"16"}]},{"v":"I39","state":"done"}]},{"say":"I6 to I7: 13 + 4 = 17, so I7's distance becomes 17. Put I7 in the queue.","ops":[{"v":"I7","state":"waiting"},{"e":["I6","I7"],"state":"tree"},{"panel":"dist","set":{"I7":"17"}},{"panel":"queue","list":[{"key":"I19","note":"13"},{"key":"I29","note":"13"},{"key":"I43","note":"13"},{"key":"I3","note":"14"},{"key":"I38","note":"14"},{"key":"I11","note":"15"},{"key":"I17","note":"15"},{"key":"I30","note":"15"},{"key":"I35","note":"15"},{"key":"I27","note":"16"},{"key":"I7","note":"17"}]}]},{"say":"Take I19 from the queue. Its distance, 13, is now final.","ops":[{"v":"I19","state":"current"},{"panel":"queue","list":[{"key":"I29","note":"13"},{"key":"I43","note":"13"},{"key":"I3","note":"14"},{"key":"I38","note":"14"},{"key":"I11","note":"15"},{"key":"I17","note":"15"},{"key":"I30","note":"15"},{"key":"I35","note":"15"},{"key":"I27","note":"16"},{"key":"I7","note":"17"}]},{"v":"I6","state":"done"}]},{"say":"I19 to I10: 13 + 5 = 18, so I10's distance becomes 18. Put I10 in the queue.","ops":[{"v":"I10","state":"waiting"},{"e":["I19","I10"],"state":"tree"},{"panel":"dist","set":{"I10":"18"}},{"panel":"queue","list":[{"key":"I29","note":"13"},{"key":"I43","note":"13"},{"key":"I3","note":"14"},{"key":"I38","note":"14"},{"key":"I11","note":"15"},{"key":"I17","note":"15"},{"key":"I30","note":"15"},{"key":"I35","note":"15"},{"key":"I27","note":"16"},{"key":"I7","note":"17"},{"key":"I10","note":"18"}]}]},{"say":"Take I29 from the queue. Its distance, 13, is now final.","ops":[{"v":"I29","state":"current"},{"panel":"queue","list":[{"key":"I43","note":"13"},{"key":"I3","note":"14"},{"key":"I38","note":"14"},{"key":"I11","note":"15"},{"key":"I17","note":"15"},{"key":"I30","note":"15"},{"key":"I35","note":"15"},{"key":"I27","note":"16"},{"key":"I7","note":"17"},{"key":"I10","note":"18"}]},{"v":"I19","state":"done"}]},{"say":"I29 to I30: 13 + 2 = 15, not shorter than 15, so I30 keeps 15.","ops":[{"e":["I29","I30"],"state":"examined"}]},{"say":"I29 to I38: 13 + 4 = 17, not shorter than 14, so I38 keeps 14.","ops":[{"e":["I29","I38"],"state":"examined"}]},{"say":"Take I43 from the queue. Its distance, 13, is now final.","ops":[{"v":"I43","state":"current"},{"panel":"queue","list":[{"key":"I3","note":"14"},{"key":"I38","note":"14"},{"key":"I11","note":"15"},{"key":"I17","note":"15"},{"key":"I30","note":"15"},{"key":"I35","note":"15"},{"key":"I27","note":"16"},{"key":"I7","note":"17"},{"key":"I10","note":"18"}]},{"v":"I29","state":"done"}]},{"say":"I43 to I42: 13 + 3 = 16, so I42's distance becomes 16. Put I42 in the queue.","ops":[{"v":"I42","state":"waiting"},{"e":["I43","I42"],"state":"tree"},{"panel":"dist","set":{"I42":"16"}},{"panel":"queue","list":[{"key":"I3","note":"14"},{"key":"I38","note":"14"},{"key":"I11","note":"15"},{"key":"I17","note":"15"},{"key":"I30","note":"15"},{"key":"I35","note":"15"},{"key":"I27","note":"16"},{"key":"I42","note":"16"},{"key":"I7","note":"17"},{"key":"I10","note":"18"}]}]},{"say":"Take I3 from the queue. Its distance, 14, is now final.","ops":[{"v":"I3","state":"current"},{"panel":"queue","list":[{"key":"I38","note":"14"},{"key":"I11","note":"15"},{"key":"I17","note":"15"},{"key":"I30","note":"15"},{"key":"I35","note":"15"},{"key":"I27","note":"16"},{"key":"I42","note":"16"},{"key":"I7","note":"17"},{"key":"I10","note":"18"}]},{"v":"I43","state":"done"}]},{"say":"I3 to I4: 14 + 3 = 17, so I4's distance becomes 17. Put I4 in the queue.","ops":[{"v":"I4","state":"waiting"},{"e":["I3","I4"],"state":"tree"},{"panel":"dist","set":{"I4":"17"}},{"panel":"queue","list":[{"key":"I38","note":"14"},{"key":"I11","note":"15"},{"key":"I17","note":"15"},{"key":"I30","note":"15"},{"key":"I35","note":"15"},{"key":"I27","note":"16"},{"key":"I42","note":"16"},{"key":"I4","note":"17"},{"key":"I7","note":"17"},{"key":"I10","note":"18"}]}]},{"say":"Take I38 from the queue. Its distance, 14, is now final.","ops":[{"v":"I38","state":"current"},{"panel":"queue","list":[{"key":"I11","note":"15"},{"key":"I17","note":"15"},{"key":"I30","note":"15"},{"key":"I35","note":"15"},{"key":"I27","note":"16"},{"key":"I42","note":"16"},{"key":"I4","note":"17"},{"key":"I7","note":"17"},{"key":"I10","note":"18"}]},{"v":"I3","state":"done"}]},{"say":"I38 to I37: 14 + 3 = 17, so I37's distance becomes 17. Put I37 in the queue.","ops":[{"v":"I37","state":"waiting"},{"e":["I38","I37"],"state":"tree"},{"panel":"dist","set":{"I37":"17"}},{"panel":"queue","list":[{"key":"I11","note":"15"},{"key":"I17","note":"15"},{"key":"I30","note":"15"},{"key":"I35","note":"15"},{"key":"I27","note":"16"},{"key":"I42","note":"16"},{"key":"I4","note":"17"},{"key":"I7","note":"17"},{"key":"I37","note":"17"},{"key":"I10","note":"18"}]}]},{"say":"Take I11 from the queue. Its distance, 15, is now final.","ops":[{"v":"I11","state":"current"},{"panel":"queue","list":[{"key":"I17","note":"15"},{"key":"I30","note":"15"},{"key":"I35","note":"15"},{"key":"I27","note":"16"},{"key":"I42","note":"16"},{"key":"I4","note":"17"},{"key":"I7","note":"17"},{"key":"I37","note":"17"},{"key":"I10","note":"18"}]},{"v":"I38","state":"done"}]},{"say":"I11 to I10: 15 + 4 = 19, not shorter than 18, so I10 keeps 18.","ops":[{"e":["I11","I10"],"state":"examined"}]},{"say":"Take I17 from the queue. Its distance, 15, is now final.","ops":[{"v":"I17","state":"current"},{"panel":"queue","list":[{"key":"I30","note":"15"},{"key":"I35","note":"15"},{"key":"I27","note":"16"},{"key":"I42","note":"16"},{"key":"I4","note":"17"},{"key":"I7","note":"17"},{"key":"I37","note":"17"},{"key":"I10","note":"18"}]},{"v":"I11","state":"done"}]},{"say":"I17 to I8: 15 + 5 = 20, so I8's distance becomes 20. Put I8 in the queue.","ops":[{"v":"I8","state":"waiting"},{"e":["I17","I8"],"state":"tree"},{"panel":"dist","set":{"I8":"20"}},{"panel":"queue","list":[{"key":"I30","note":"15"},{"key":"I35","note":"15"},{"key":"I27","note":"16"},{"key":"I42","note":"16"},{"key":"I4","note":"17"},{"key":"I7","note":"17"},{"key":"I37","note":"17"},{"key":"I10","note":"18"},{"key":"I8","note":"20"}]}]},{"say":"I17 to I16: 15 + 2 = 17, so I16's distance becomes 17. Put I16 in the queue.","ops":[{"v":"I16","state":"waiting"},{"e":["I17","I16"],"state":"tree"},{"panel":"dist","set":{"I16":"17"}},{"panel":"queue","list":[{"key":"I30","note":"15"},{"key":"I35","note":"15"},{"key":"I27","note":"16"},{"key":"I42","note":"16"},{"key":"I4","note":"17"},{"key":"I7","note":"17"},{"key":"I16","note":"17"},{"key":"I37","note":"17"},{"key":"I10","note":"18"},{"key":"I8","note":"20"}]}]},{"say":"Take I30 from the queue. Its distance, 15, is now final. It has no unsettled neighbors.","ops":[{"v":"I30","state":"current"},{"panel":"queue","list":[{"key":"I35","note":"15"},{"key":"I27","note":"16"},{"key":"I42","note":"16"},{"key":"I4","note":"17"},{"key":"I7","note":"17"},{"key":"I16","note":"17"},{"key":"I37","note":"17"},{"key":"I10","note":"18"},{"key":"I8","note":"20"}]},{"v":"I17","state":"done"}]},{"say":"Take I35 from the queue. Its distance, 15, is now final.","ops":[{"v":"I35","state":"current"},{"panel":"queue","list":[{"key":"I27","note":"16"},{"key":"I42","note":"16"},{"key":"I4","note":"17"},{"key":"I7","note":"17"},{"key":"I16","note":"17"},{"key":"I37","note":"17"},{"key":"I10","note":"18"},{"key":"I8","note":"20"}]},{"v":"I30","state":"done"}]},{"say":"I35 to I36: 15 + 5 = 20, so I36's distance becomes 20. Put I36 in the queue.","ops":[{"v":"I36","state":"waiting"},{"e":["I35","I36"],"state":"tree"},{"panel":"dist","set":{"I36":"20"}},{"panel":"queue","list":[{"key":"I27","note":"16"},{"key":"I42","note":"16"},{"key":"I4","note":"17"},{"key":"I7","note":"17"},{"key":"I16","note":"17"},{"key":"I37","note":"17"},{"key":"I10","note":"18"},{"key":"I8","note":"20"},{"key":"I36","note":"20"}]}]},{"say":"Take I27 from the queue. Its distance, 16, is now final.","ops":[{"v":"I27","state":"current"},{"panel":"queue","list":[{"key":"I42","note":"16"},{"key":"I4","note":"17"},{"key":"I7","note":"17"},{"key":"I16","note":"17"},{"key":"I37","note":"17"},{"key":"I10","note":"18"},{"key":"I8","note":"20"},{"key":"I36","note":"20"}]},{"v":"I35","state":"done"}]},{"say":"I27 to I36: 16 + 3 = 19, shorter than 20, so I36's distance becomes 19. Move I36 up the queue.","ops":[{"e":["I27","I36"],"state":"tree"},{"e":["I35","I36"],"state":"examined"},{"panel":"dist","set":{"I36":"19"}},{"panel":"queue","list":[{"key":"I42","note":"16"},{"key":"I4","note":"17"},{"key":"I7","note":"17"},{"key":"I16","note":"17"},{"key":"I37","note":"17"},{"key":"I10","note":"18"},{"key":"I36","note":"19"},{"key":"I8","note":"20"}]}]},{"say":"Take I42 from the queue. Its distance, 16, is now final. It has no unsettled neighbors.","ops":[{"v":"I42","state":"current"},{"panel":"queue","list":[{"key":"I4","note":"17"},{"key":"I7","note":"17"},{"key":"I16","note":"17"},{"key":"I37","note":"17"},{"key":"I10","note":"18"},{"key":"I36","note":"19"},{"key":"I8","note":"20"}]},{"v":"I27","state":"done"}]},{"say":"Take I4 from the queue. Its distance, 17, is now final. It has no unsettled neighbors.","ops":[{"v":"I4","state":"current"},{"panel":"queue","list":[{"key":"I7","note":"17"},{"key":"I16","note":"17"},{"key":"I37","note":"17"},{"key":"I10","note":"18"},{"key":"I36","note":"19"},{"key":"I8","note":"20"}]},{"v":"I42","state":"done"}]},{"say":"Take I7 from the queue. Its distance, 17, is now final.","ops":[{"v":"I7","state":"current"},{"panel":"queue","list":[{"key":"I16","note":"17"},{"key":"I37","note":"17"},{"key":"I10","note":"18"},{"key":"I36","note":"19"},{"key":"I8","note":"20"}]},{"v":"I4","state":"done"}]},{"say":"I7 to I8: 17 + 4 = 21, not shorter than 20, so I8 keeps 20.","ops":[{"e":["I7","I8"],"state":"examined"}]},{"say":"I7 to I16: 17 + 3 = 20, not shorter than 17, so I16 keeps 17.","ops":[{"e":["I7","I16"],"state":"examined"}]},{"say":"Take I16 from the queue. Its distance, 17, is now final. It has no unsettled neighbors.","ops":[{"v":"I16","state":"current"},{"panel":"queue","list":[{"key":"I37","note":"17"},{"key":"I10","note":"18"},{"key":"I36","note":"19"},{"key":"I8","note":"20"}]},{"v":"I7","state":"done"}]},{"say":"Take I37 from the queue. Its distance, 17, is now final.","ops":[{"v":"I37","state":"current"},{"panel":"queue","list":[{"key":"I10","note":"18"},{"key":"I36","note":"19"},{"key":"I8","note":"20"}]},{"v":"I16","state":"done"}]},{"say":"I37 to I28: 17 + 4 = 21, so I28's distance becomes 21. Put I28 in the queue.","ops":[{"v":"I28","state":"waiting"},{"e":["I37","I28"],"state":"tree"},{"panel":"dist","set":{"I28":"21"}},{"panel":"queue","list":[{"key":"I10","note":"18"},{"key":"I36","note":"19"},{"key":"I8","note":"20"},{"key":"I28","note":"21"}]}]},{"say":"Take I10 from the queue. Its distance, 18, is now final.","ops":[{"v":"I10","state":"current"},{"panel":"queue","list":[{"key":"I36","note":"19"},{"key":"I8","note":"20"},{"key":"I28","note":"21"}]},{"v":"I37","state":"done"}]},{"say":"I10 to I1: 18 + 5 = 23, so I1's distance becomes 23. Put I1 in the queue.","ops":[{"v":"I1","state":"waiting"},{"e":["I10","I1"],"state":"tree"},{"panel":"dist","set":{"I1":"23"}},{"panel":"queue","list":[{"key":"I36","note":"19"},{"key":"I8","note":"20"},{"key":"I28","note":"21"},{"key":"I1","note":"23"}]}]},{"say":"Take I36 from the queue. Its distance, 19, is now final.","ops":[{"v":"I36","state":"current"},{"panel":"queue","list":[{"key":"I8","note":"20"},{"key":"I28","note":"21"},{"key":"I1","note":"23"}]},{"v":"I10","state":"done"}]},{"say":"I36 to I45: 19 + 2 = 21, so I45's distance becomes 21. Put I45 in the queue.","ops":[{"v":"I45","state":"waiting"},{"e":["I36","I45"],"state":"tree"},{"panel":"dist","set":{"I45":"21"}},{"panel":"queue","list":[{"key":"I8","note":"20"},{"key":"I28","note":"21"},{"key":"I45","note":"21"},{"key":"I1","note":"23"}]}]},{"say":"Take I8 from the queue. Its distance, 20, is now final.","ops":[{"v":"I8","state":"current"},{"panel":"queue","list":[{"key":"I28","note":"21"},{"key":"I45","note":"21"},{"key":"I1","note":"23"}]},{"v":"I36","state":"done"}]},{"say":"I8 to I9: 20 + 4 = 24, so I9's distance becomes 24. Put I9 in the queue.","ops":[{"v":"I9","state":"waiting"},{"e":["I8","I9"],"state":"tree"},{"panel":"dist","set":{"I9":"24"}},{"panel":"queue","list":[{"key":"I28","note":"21"},{"key":"I45","note":"21"},{"key":"I1","note":"23"},{"key":"I9","note":"24"}]}]},{"say":"Take I28 from the queue. Its distance, 21, is now final. It has no unsettled neighbors.","ops":[{"v":"I28","state":"current"},{"panel":"queue","list":[{"key":"I45","note":"21"},{"key":"I1","note":"23"},{"key":"I9","note":"24"}]},{"v":"I8","state":"done"}]},{"say":"Take I45 from the queue. Its distance, 21, is now final.","ops":[{"v":"I45","state":"current"},{"panel":"queue","list":[{"key":"I1","note":"23"},{"key":"I9","note":"24"}]},{"v":"I28","state":"done"}]},{"say":"I45 to I44: 21 + 3 = 24, so I44's distance becomes 24. Put I44 in the queue.","ops":[{"v":"I44","state":"waiting"},{"e":["I45","I44"],"state":"tree"},{"panel":"dist","set":{"I44":"24"}},{"panel":"queue","list":[{"key":"I1","note":"23"},{"key":"I9","note":"24"},{"key":"I44","note":"24"}]}]},{"say":"Take I1 from the queue. Its distance, 23, is now final.","ops":[{"v":"I1","state":"current"},{"panel":"queue","list":[{"key":"I9","note":"24"},{"key":"I44","note":"24"}]},{"v":"I45","state":"done"}]},{"say":"I1 to I2: 23 + 3 = 26, so I2's distance becomes 26. Put I2 in the queue.","ops":[{"v":"I2","state":"waiting"},{"e":["I1","I2"],"state":"tree"},{"panel":"dist","set":{"I2":"26"}},{"panel":"queue","list":[{"key":"I9","note":"24"},{"key":"I44","note":"24"},{"key":"I2","note":"26"}]}]},{"say":"Take I9 from the queue. Its distance, 24, is now final.","ops":[{"v":"I9","state":"current"},{"panel":"queue","list":[{"key":"I44","note":"24"},{"key":"I2","note":"26"}]},{"v":"I1","state":"done"}]},{"say":"I9 to I18: 24 + 2 = 26, so I18's distance becomes 26. Put I18 in the queue.","ops":[{"v":"I18","state":"waiting"},{"e":["I9","I18"],"state":"tree"},{"panel":"dist","set":{"I18":"26"}},{"panel":"queue","list":[{"key":"I44","note":"24"},{"key":"I2","note":"26"},{"key":"I18","note":"26"}]}]},{"say":"Take I44 from the queue. Its distance, 24, is now final. It has no unsettled neighbors.","ops":[{"v":"I44","state":"current"},{"panel":"queue","list":[{"key":"I2","note":"26"},{"key":"I18","note":"26"}]},{"v":"I9","state":"done"}]},{"say":"Take I2 from the queue. Its distance, 26, is now final. It has no unsettled neighbors.","ops":[{"v":"I2","state":"current"},{"panel":"queue","list":[{"key":"I18","note":"26"}]},{"v":"I44","state":"done"}]},{"say":"Take I18 from the queue. Its distance, 26, is now final. It has no unsettled neighbors.","ops":[{"v":"I18","state":"current"},{"panel":"queue","list":[]},{"v":"I2","state":"done"}]},{"say":"Done. Every distance from I23 is final.","ops":[{"v":"I18","state":"done"}]}],"traceNote":"","verification":"The steps come from a step-by-step copy of the algorithm. Its distances and the route it draws to each vertex are checked against Distance and PathTo of path.DijkstraPaths on every start.","snippet":"paths, err := path.DijkstraPaths(g, \"I23\")\nif err != nil {\n\treturn err\n}\nminutes, ok := paths.Distance(\"I2\")\nif !ok {\n\treturn nil // out of reach\n}\nroute, _ := paths.PathTo(\"I2\")\nfmt.Println(minutes)\nfor _, v := range route {\n\tfmt.Println(v.Label())\n}"}
