{"algorithm":"multi-source-dijkstra","about":["Multi-source Dijkstra answers which source is nearest to each vertex, such as which warehouse can reach each address soonest. It puts every source in the queue at distance 0 and then runs Dijkstra's algorithm once. Each vertex is settled by whichever source gets there first, so the areas around the sources grow together until they meet.","One search settles each vertex once, so it costs O((V+E) log V) however many sources there are. Running path.Dijkstra from each source instead settles every vertex once per source. The performance card on this page times both.","path.DijkstraMultiSource returns a NearestSources value with Source, Distance and PathTo for any vertex. When two sources are equally near, the one listed first wins, so the same sources give the same answer on every run. Distances run along the edges, from a source to the vertex. On a map with one-way streets, that is the drive from the warehouse to the address, and the drive back can differ."],"template":{"id":"downtown-grid","name":"Downtown grid","description":"Twenty intersections on a downtown street grid. Streets go both ways, Market is closed to cars between 2nd and 3rd, and each edge is the travel time in minutes.","family":"road","directed":true,"weighted":true,"acyclic":false,"vertices":[{"id":"Pine & 1st","x":76,"y":156},{"id":"Pine & 2nd","x":283,"y":188},{"id":"Pine & 3rd","x":496,"y":189},{"id":"Pine & 4th","x":706,"y":160},{"id":"Pine & 5th","x":931,"y":161},{"id":"Main & 1st","x":68,"y":383},{"id":"Main & 2nd","x":268,"y":404},{"id":"Main & 3rd","x":518,"y":374},{"id":"Main & 4th","x":739,"y":393},{"id":"Main & 5th","x":946,"y":381},{"id":"Market & 1st","x":73,"y":597},{"id":"Market & 2nd","x":276,"y":620},{"id":"Market & 3rd","x":512,"y":609},{"id":"Market & 4th","x":704,"y":593},{"id":"Market & 5th","x":958,"y":591},{"id":"River & 1st","x":53,"y":842},{"id":"River & 2nd","x":274,"y":833},{"id":"River & 3rd","x":489,"y":826},{"id":"River & 4th","x":701,"y":833},{"id":"River & 5th","x":950,"y":829}],"edges":[{"from":"Pine & 1st","to":"Pine & 2nd","weight":2},{"from":"Pine & 2nd","to":"Pine & 1st","weight":2},{"from":"Pine & 1st","to":"Main & 1st","weight":2},{"from":"Main & 1st","to":"Pine & 1st","weight":2},{"from":"Pine & 2nd","to":"Pine & 3rd","weight":3},{"from":"Pine & 3rd","to":"Pine & 2nd","weight":3},{"from":"Pine & 2nd","to":"Main & 2nd","weight":3},{"from":"Main & 2nd","to":"Pine & 2nd","weight":3},{"from":"Pine & 3rd","to":"Pine & 4th","weight":2},{"from":"Pine & 4th","to":"Pine & 3rd","weight":2},{"from":"Pine & 3rd","to":"Main & 3rd","weight":2},{"from":"Main & 3rd","to":"Pine & 3rd","weight":2},{"from":"Pine & 4th","to":"Pine & 5th","weight":3},{"from":"Pine & 5th","to":"Pine & 4th","weight":3},{"from":"Pine & 4th","to":"Main & 4th","weight":2},{"from":"Main & 4th","to":"Pine & 4th","weight":2},{"from":"Pine & 5th","to":"Main & 5th","weight":3},{"from":"Main & 5th","to":"Pine & 5th","weight":3},{"from":"Main & 1st","to":"Main & 2nd","weight":3},{"from":"Main & 2nd","to":"Main & 1st","weight":3},{"from":"Main & 1st","to":"Market & 1st","weight":3},{"from":"Market & 1st","to":"Main & 1st","weight":3},{"from":"Main & 2nd","to":"Main & 3rd","weight":4},{"from":"Main & 3rd","to":"Main & 2nd","weight":4},{"from":"Main & 2nd","to":"Market & 2nd","weight":2},{"from":"Market & 2nd","to":"Main & 2nd","weight":2},{"from":"Main & 3rd","to":"Main & 4th","weight":4},{"from":"Main & 4th","to":"Main & 3rd","weight":4},{"from":"Main & 3rd","to":"Market & 3rd","weight":3},{"from":"Market & 3rd","to":"Main & 3rd","weight":3},{"from":"Main & 4th","to":"Main & 5th","weight":3},{"from":"Main & 5th","to":"Main & 4th","weight":3},{"from":"Main & 4th","to":"Market & 4th","weight":2},{"from":"Market & 4th","to":"Main & 4th","weight":2},{"from":"Main & 5th","to":"Market & 5th","weight":2},{"from":"Market & 5th","to":"Main & 5th","weight":2},{"from":"Market & 1st","to":"Market & 2nd","weight":2},{"from":"Market & 2nd","to":"Market & 1st","weight":2},{"from":"Market & 1st","to":"River & 1st","weight":2},{"from":"River & 1st","to":"Market & 1st","weight":2},{"from":"Market & 2nd","to":"River & 2nd","weight":2},{"from":"River & 2nd","to":"Market & 2nd","weight":2},{"from":"Market & 3rd","to":"Market & 4th","weight":3},{"from":"Market & 4th","to":"Market & 3rd","weight":3},{"from":"Market & 3rd","to":"River & 3rd","weight":3},{"from":"River & 3rd","to":"Market & 3rd","weight":3},{"from":"Market & 4th","to":"Market & 5th","weight":2},{"from":"Market & 5th","to":"Market & 4th","weight":2},{"from":"Market & 4th","to":"River & 4th","weight":3},{"from":"River & 4th","to":"Market & 4th","weight":3},{"from":"Market & 5th","to":"River & 5th","weight":2},{"from":"River & 5th","to":"Market & 5th","weight":2},{"from":"River & 1st","to":"River & 2nd","weight":3},{"from":"River & 2nd","to":"River & 1st","weight":3},{"from":"River & 2nd","to":"River & 3rd","weight":2},{"from":"River & 3rd","to":"River & 2nd","weight":2},{"from":"River & 3rd","to":"River & 4th","weight":2},{"from":"River & 4th","to":"River & 3rd","weight":2},{"from":"River & 4th","to":"River & 5th","weight":4},{"from":"River & 5th","to":"River & 4th","weight":4}],"details":{"vertices":20,"edges":60,"directed":true,"weighted":true,"acyclic":false,"weightMin":2,"weightMax":4,"negativeWeights":false,"density":0.15789473684210525,"inDegree":{"min":2,"avg":3,"max":4},"outDegree":{"min":2,"avg":3,"max":4},"selfLoops":0,"components":1}},"problem":"With warehouses at opposite corners of downtown, which one should deliver to each intersection, and what is the longest drive?","params":{"sources":["Pine & 1st","River & 5th"]},"result":{"kind":"groups","groups":[["Main \u0026 1st","Main \u0026 2nd","Main \u0026 3rd","Market \u0026 1st","Market \u0026 2nd","Pine \u0026 1st","Pine \u0026 2nd","Pine \u0026 3rd","Pine \u0026 4th","River \u0026 1st"],["Main \u0026 4th","Main \u0026 5th","Market \u0026 3rd","Market \u0026 4th","Market \u0026 5th","Pine \u0026 5th","River \u0026 2nd","River \u0026 3rd","River \u0026 4th","River \u0026 5th"]]},"answer":"Warehouse 1 at Pine & 1st serves 10 and 2 at River & 5th serves 10. The longest drive is 8, from warehouse 2 to River & 2nd.","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":"component-1","label":"Warehouse 1, serves 10","color":"#009E73","shape":"filled"},{"id":"component-2","label":"Warehouse 2, serves 10","color":"#CC79A7","shape":"filled"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"examined","label":"Checked, not quicker","color":"#64748B","shape":"dashed"},{"id":"area-1","label":"Road from warehouse 1","color":"#009E73","shape":"thick"},{"id":"area-2","label":"Road from warehouse 2","color":"#CC79A7","shape":"thick"}],"panels":[{"id":"queue","title":"Priority queue","kind":"list"},{"id":"dist","title":"Drive time","kind":"table"},{"id":"areas","title":"Areas","kind":"groups"}]},"steps":[{"say":"Put every warehouse in the queue at 0: 1 at Pine & 1st and 2 at River & 5th. Each place goes to the warehouse that can reach it soonest, so one search serves them all.","ops":[{"panel":"dist","set":{"Pine & 1st":"∞"}},{"panel":"dist","set":{"Pine & 2nd":"∞"}},{"panel":"dist","set":{"Pine & 3rd":"∞"}},{"panel":"dist","set":{"Pine & 4th":"∞"}},{"panel":"dist","set":{"Pine & 5th":"∞"}},{"panel":"dist","set":{"Main & 1st":"∞"}},{"panel":"dist","set":{"Main & 2nd":"∞"}},{"panel":"dist","set":{"Main & 3rd":"∞"}},{"panel":"dist","set":{"Main & 4th":"∞"}},{"panel":"dist","set":{"Main & 5th":"∞"}},{"panel":"dist","set":{"Market & 1st":"∞"}},{"panel":"dist","set":{"Market & 2nd":"∞"}},{"panel":"dist","set":{"Market & 3rd":"∞"}},{"panel":"dist","set":{"Market & 4th":"∞"}},{"panel":"dist","set":{"Market & 5th":"∞"}},{"panel":"dist","set":{"River & 1st":"∞"}},{"panel":"dist","set":{"River & 2nd":"∞"}},{"panel":"dist","set":{"River & 3rd":"∞"}},{"panel":"dist","set":{"River & 4th":"∞"}},{"panel":"dist","set":{"River & 5th":"∞"}},{"v":"Pine & 1st","state":"waiting"},{"panel":"dist","set":{"Pine & 1st":"0"}},{"v":"River & 5th","state":"waiting"},{"panel":"dist","set":{"River & 5th":"0"}},{"panel":"queue","list":[{"key":"Pine & 1st","note":"0"},{"key":"River & 5th","note":"0"}]}]},{"say":"Take Pine & 1st from the queue. It is warehouse 1, at 0 from itself.","ops":[{"v":"Pine & 1st","state":"current"},{"panel":"queue","list":[{"key":"River & 5th","note":"0"}]},{"panel":"areas","groups":[["Pine & 1st"]]}]},{"say":"Pine & 1st to Pine & 2nd: 0 + 2 = 2, so Pine & 2nd goes to warehouse 1 at 2.","ops":[{"e":["Pine & 1st","Pine & 2nd"],"state":"area-1"},{"panel":"dist","set":{"Pine & 2nd":"2"}},{"panel":"queue","list":[{"key":"River & 5th","note":"0"},{"key":"Pine & 2nd","note":"2"}]},{"v":"Pine & 2nd","state":"waiting"}]},{"say":"Pine & 1st to Main & 1st: 0 + 2 = 2, so Main & 1st goes to warehouse 1 at 2.","ops":[{"e":["Pine & 1st","Main & 1st"],"state":"area-1"},{"panel":"dist","set":{"Main & 1st":"2"}},{"panel":"queue","list":[{"key":"River & 5th","note":"0"},{"key":"Pine & 2nd","note":"2"},{"key":"Main & 1st","note":"2"}]},{"v":"Main & 1st","state":"waiting"}]},{"say":"Take River & 5th from the queue. It is warehouse 2, at 0 from itself.","ops":[{"v":"River & 5th","state":"current"},{"panel":"queue","list":[{"key":"Pine & 2nd","note":"2"},{"key":"Main & 1st","note":"2"}]},{"v":"Pine & 1st","state":"component-1"},{"panel":"areas","groups":[["Pine & 1st"],["River & 5th"]]}]},{"say":"River & 5th to Market & 5th: 0 + 2 = 2, so Market & 5th goes to warehouse 2 at 2.","ops":[{"e":["River & 5th","Market & 5th"],"state":"area-2"},{"panel":"dist","set":{"Market & 5th":"2"}},{"panel":"queue","list":[{"key":"Pine & 2nd","note":"2"},{"key":"Main & 1st","note":"2"},{"key":"Market & 5th","note":"2"}]},{"v":"Market & 5th","state":"waiting"}]},{"say":"River & 5th to River & 4th: 0 + 4 = 4, so River & 4th goes to warehouse 2 at 4.","ops":[{"e":["River & 5th","River & 4th"],"state":"area-2"},{"panel":"dist","set":{"River & 4th":"4"}},{"panel":"queue","list":[{"key":"Pine & 2nd","note":"2"},{"key":"Main & 1st","note":"2"},{"key":"Market & 5th","note":"2"},{"key":"River & 4th","note":"4"}]},{"v":"River & 4th","state":"waiting"}]},{"say":"Take Pine & 2nd from the queue. Warehouse 1 reaches it in 2, and nothing reaches it sooner.","ops":[{"v":"Pine & 2nd","state":"current"},{"panel":"queue","list":[{"key":"Main & 1st","note":"2"},{"key":"Market & 5th","note":"2"},{"key":"River & 4th","note":"4"}]},{"v":"River & 5th","state":"component-2"},{"panel":"areas","groups":[["Pine & 1st","Pine & 2nd"],["River & 5th"]]}]},{"say":"Pine & 2nd to Pine & 3rd: 2 + 3 = 5, so Pine & 3rd goes to warehouse 1 at 5.","ops":[{"e":["Pine & 2nd","Pine & 3rd"],"state":"area-1"},{"panel":"dist","set":{"Pine & 3rd":"5"}},{"panel":"queue","list":[{"key":"Main & 1st","note":"2"},{"key":"Market & 5th","note":"2"},{"key":"River & 4th","note":"4"},{"key":"Pine & 3rd","note":"5"}]},{"v":"Pine & 3rd","state":"waiting"}]},{"say":"Pine & 2nd to Main & 2nd: 2 + 3 = 5, so Main & 2nd goes to warehouse 1 at 5.","ops":[{"e":["Pine & 2nd","Main & 2nd"],"state":"area-1"},{"panel":"dist","set":{"Main & 2nd":"5"}},{"panel":"queue","list":[{"key":"Main & 1st","note":"2"},{"key":"Market & 5th","note":"2"},{"key":"River & 4th","note":"4"},{"key":"Pine & 3rd","note":"5"},{"key":"Main & 2nd","note":"5"}]},{"v":"Main & 2nd","state":"waiting"}]},{"say":"Take Main & 1st from the queue. Warehouse 1 reaches it in 2, and nothing reaches it sooner.","ops":[{"v":"Main & 1st","state":"current"},{"panel":"queue","list":[{"key":"Market & 5th","note":"2"},{"key":"River & 4th","note":"4"},{"key":"Pine & 3rd","note":"5"},{"key":"Main & 2nd","note":"5"}]},{"v":"Pine & 2nd","state":"component-1"},{"panel":"areas","groups":[["Pine & 1st","Pine & 2nd","Main & 1st"],["River & 5th"]]}]},{"say":"Main & 1st to Main & 2nd: 2 + 3 = 5, not quicker than 5, so Main & 2nd stays with warehouse 1.","ops":[{"e":["Main & 1st","Main & 2nd"],"state":"examined"}]},{"say":"Main & 1st to Market & 1st: 2 + 3 = 5, so Market & 1st goes to warehouse 1 at 5.","ops":[{"e":["Main & 1st","Market & 1st"],"state":"area-1"},{"panel":"dist","set":{"Market & 1st":"5"}},{"panel":"queue","list":[{"key":"Market & 5th","note":"2"},{"key":"River & 4th","note":"4"},{"key":"Pine & 3rd","note":"5"},{"key":"Main & 2nd","note":"5"},{"key":"Market & 1st","note":"5"}]},{"v":"Market & 1st","state":"waiting"}]},{"say":"Take Market & 5th from the queue. Warehouse 2 reaches it in 2, and nothing reaches it sooner.","ops":[{"v":"Market & 5th","state":"current"},{"panel":"queue","list":[{"key":"River & 4th","note":"4"},{"key":"Pine & 3rd","note":"5"},{"key":"Main & 2nd","note":"5"},{"key":"Market & 1st","note":"5"}]},{"v":"Main & 1st","state":"component-1"},{"panel":"areas","groups":[["Pine & 1st","Pine & 2nd","Main & 1st"],["River & 5th","Market & 5th"]]}]},{"say":"Market & 5th to Main & 5th: 2 + 2 = 4, so Main & 5th goes to warehouse 2 at 4.","ops":[{"e":["Market & 5th","Main & 5th"],"state":"area-2"},{"panel":"dist","set":{"Main & 5th":"4"}},{"panel":"queue","list":[{"key":"Main & 5th","note":"4"},{"key":"River & 4th","note":"4"},{"key":"Pine & 3rd","note":"5"},{"key":"Main & 2nd","note":"5"},{"key":"Market & 1st","note":"5"}]},{"v":"Main & 5th","state":"waiting"}]},{"say":"Market & 5th to Market & 4th: 2 + 2 = 4, so Market & 4th goes to warehouse 2 at 4.","ops":[{"e":["Market & 5th","Market & 4th"],"state":"area-2"},{"panel":"dist","set":{"Market & 4th":"4"}},{"panel":"queue","list":[{"key":"Main & 5th","note":"4"},{"key":"Market & 4th","note":"4"},{"key":"River & 4th","note":"4"},{"key":"Pine & 3rd","note":"5"},{"key":"Main & 2nd","note":"5"},{"key":"Market & 1st","note":"5"}]},{"v":"Market & 4th","state":"waiting"}]},{"say":"Take Main & 5th from the queue. Warehouse 2 reaches it in 4, and nothing reaches it sooner.","ops":[{"v":"Main & 5th","state":"current"},{"panel":"queue","list":[{"key":"Market & 4th","note":"4"},{"key":"River & 4th","note":"4"},{"key":"Pine & 3rd","note":"5"},{"key":"Main & 2nd","note":"5"},{"key":"Market & 1st","note":"5"}]},{"v":"Market & 5th","state":"component-2"},{"panel":"areas","groups":[["Pine & 1st","Pine & 2nd","Main & 1st"],["River & 5th","Market & 5th","Main & 5th"]]}]},{"say":"Main & 5th to Pine & 5th: 4 + 3 = 7, so Pine & 5th goes to warehouse 2 at 7.","ops":[{"e":["Main & 5th","Pine & 5th"],"state":"area-2"},{"panel":"dist","set":{"Pine & 5th":"7"}},{"panel":"queue","list":[{"key":"Market & 4th","note":"4"},{"key":"River & 4th","note":"4"},{"key":"Pine & 3rd","note":"5"},{"key":"Main & 2nd","note":"5"},{"key":"Market & 1st","note":"5"},{"key":"Pine & 5th","note":"7"}]},{"v":"Pine & 5th","state":"waiting"}]},{"say":"Main & 5th to Main & 4th: 4 + 3 = 7, so Main & 4th goes to warehouse 2 at 7.","ops":[{"e":["Main & 5th","Main & 4th"],"state":"area-2"},{"panel":"dist","set":{"Main & 4th":"7"}},{"panel":"queue","list":[{"key":"Market & 4th","note":"4"},{"key":"River & 4th","note":"4"},{"key":"Pine & 3rd","note":"5"},{"key":"Main & 2nd","note":"5"},{"key":"Market & 1st","note":"5"},{"key":"Pine & 5th","note":"7"},{"key":"Main & 4th","note":"7"}]},{"v":"Main & 4th","state":"waiting"}]},{"say":"Take Market & 4th from the queue. Warehouse 2 reaches it in 4, and nothing reaches it sooner.","ops":[{"v":"Market & 4th","state":"current"},{"panel":"queue","list":[{"key":"River & 4th","note":"4"},{"key":"Pine & 3rd","note":"5"},{"key":"Main & 2nd","note":"5"},{"key":"Market & 1st","note":"5"},{"key":"Pine & 5th","note":"7"},{"key":"Main & 4th","note":"7"}]},{"v":"Main & 5th","state":"component-2"},{"panel":"areas","groups":[["Pine & 1st","Pine & 2nd","Main & 1st"],["River & 5th","Market & 5th","Main & 5th","Market & 4th"]]}]},{"say":"Market & 4th to Main & 4th: 4 + 2 = 6, quicker than 7 from warehouse 2, so Main & 4th goes to warehouse 2 at 6.","ops":[{"e":["Market & 4th","Main & 4th"],"state":"area-2"},{"panel":"dist","set":{"Main & 4th":"6"}},{"panel":"queue","list":[{"key":"River & 4th","note":"4"},{"key":"Pine & 3rd","note":"5"},{"key":"Main & 2nd","note":"5"},{"key":"Market & 1st","note":"5"},{"key":"Main & 4th","note":"6"},{"key":"Pine & 5th","note":"7"}]},{"e":["Main & 5th","Main & 4th"],"state":"examined"}]},{"say":"Market & 4th to Market & 3rd: 4 + 3 = 7, so Market & 3rd goes to warehouse 2 at 7.","ops":[{"e":["Market & 4th","Market & 3rd"],"state":"area-2"},{"panel":"dist","set":{"Market & 3rd":"7"}},{"panel":"queue","list":[{"key":"River & 4th","note":"4"},{"key":"Pine & 3rd","note":"5"},{"key":"Main & 2nd","note":"5"},{"key":"Market & 1st","note":"5"},{"key":"Main & 4th","note":"6"},{"key":"Pine & 5th","note":"7"},{"key":"Market & 3rd","note":"7"}]},{"v":"Market & 3rd","state":"waiting"}]},{"say":"Market & 4th to River & 4th: 4 + 3 = 7, not quicker than 4, so River & 4th stays with warehouse 2.","ops":[{"e":["Market & 4th","River & 4th"],"state":"examined"}]},{"say":"Take River & 4th from the queue. Warehouse 2 reaches it in 4, and nothing reaches it sooner.","ops":[{"v":"River & 4th","state":"current"},{"panel":"queue","list":[{"key":"Pine & 3rd","note":"5"},{"key":"Main & 2nd","note":"5"},{"key":"Market & 1st","note":"5"},{"key":"Main & 4th","note":"6"},{"key":"Pine & 5th","note":"7"},{"key":"Market & 3rd","note":"7"}]},{"v":"Market & 4th","state":"component-2"},{"panel":"areas","groups":[["Pine & 1st","Pine & 2nd","Main & 1st"],["River & 5th","Market & 5th","Main & 5th","Market & 4th","River & 4th"]]}]},{"say":"River & 4th to River & 3rd: 4 + 2 = 6, so River & 3rd goes to warehouse 2 at 6.","ops":[{"e":["River & 4th","River & 3rd"],"state":"area-2"},{"panel":"dist","set":{"River & 3rd":"6"}},{"panel":"queue","list":[{"key":"Pine & 3rd","note":"5"},{"key":"Main & 2nd","note":"5"},{"key":"Market & 1st","note":"5"},{"key":"Main & 4th","note":"6"},{"key":"River & 3rd","note":"6"},{"key":"Pine & 5th","note":"7"},{"key":"Market & 3rd","note":"7"}]},{"v":"River & 3rd","state":"waiting"}]},{"say":"Take Pine & 3rd from the queue. Warehouse 1 reaches it in 5, and nothing reaches it sooner.","ops":[{"v":"Pine & 3rd","state":"current"},{"panel":"queue","list":[{"key":"Main & 2nd","note":"5"},{"key":"Market & 1st","note":"5"},{"key":"Main & 4th","note":"6"},{"key":"River & 3rd","note":"6"},{"key":"Pine & 5th","note":"7"},{"key":"Market & 3rd","note":"7"}]},{"v":"River & 4th","state":"component-2"},{"panel":"areas","groups":[["Pine & 1st","Pine & 2nd","Main & 1st","Pine & 3rd"],["River & 5th","Market & 5th","Main & 5th","Market & 4th","River & 4th"]]}]},{"say":"Pine & 3rd to Pine & 4th: 5 + 2 = 7, so Pine & 4th goes to warehouse 1 at 7.","ops":[{"e":["Pine & 3rd","Pine & 4th"],"state":"area-1"},{"panel":"dist","set":{"Pine & 4th":"7"}},{"panel":"queue","list":[{"key":"Main & 2nd","note":"5"},{"key":"Market & 1st","note":"5"},{"key":"Main & 4th","note":"6"},{"key":"River & 3rd","note":"6"},{"key":"Pine & 4th","note":"7"},{"key":"Pine & 5th","note":"7"},{"key":"Market & 3rd","note":"7"}]},{"v":"Pine & 4th","state":"waiting"}]},{"say":"Pine & 3rd to Main & 3rd: 5 + 2 = 7, so Main & 3rd goes to warehouse 1 at 7.","ops":[{"e":["Pine & 3rd","Main & 3rd"],"state":"area-1"},{"panel":"dist","set":{"Main & 3rd":"7"}},{"panel":"queue","list":[{"key":"Main & 2nd","note":"5"},{"key":"Market & 1st","note":"5"},{"key":"Main & 4th","note":"6"},{"key":"River & 3rd","note":"6"},{"key":"Pine & 4th","note":"7"},{"key":"Main & 3rd","note":"7"},{"key":"Pine & 5th","note":"7"},{"key":"Market & 3rd","note":"7"}]},{"v":"Main & 3rd","state":"waiting"}]},{"say":"Take Main & 2nd from the queue. Warehouse 1 reaches it in 5, and nothing reaches it sooner.","ops":[{"v":"Main & 2nd","state":"current"},{"panel":"queue","list":[{"key":"Market & 1st","note":"5"},{"key":"Main & 4th","note":"6"},{"key":"River & 3rd","note":"6"},{"key":"Pine & 4th","note":"7"},{"key":"Main & 3rd","note":"7"},{"key":"Pine & 5th","note":"7"},{"key":"Market & 3rd","note":"7"}]},{"v":"Pine & 3rd","state":"component-1"},{"panel":"areas","groups":[["Pine & 1st","Pine & 2nd","Main & 1st","Pine & 3rd","Main & 2nd"],["River & 5th","Market & 5th","Main & 5th","Market & 4th","River & 4th"]]}]},{"say":"Main & 2nd to Main & 3rd: 5 + 4 = 9, not quicker than 7, so Main & 3rd stays with warehouse 1.","ops":[{"e":["Main & 2nd","Main & 3rd"],"state":"examined"}]},{"say":"Main & 2nd to Market & 2nd: 5 + 2 = 7, so Market & 2nd goes to warehouse 1 at 7.","ops":[{"e":["Main & 2nd","Market & 2nd"],"state":"area-1"},{"panel":"dist","set":{"Market & 2nd":"7"}},{"panel":"queue","list":[{"key":"Market & 1st","note":"5"},{"key":"Main & 4th","note":"6"},{"key":"River & 3rd","note":"6"},{"key":"Pine & 4th","note":"7"},{"key":"Main & 3rd","note":"7"},{"key":"Market & 2nd","note":"7"},{"key":"Pine & 5th","note":"7"},{"key":"Market & 3rd","note":"7"}]},{"v":"Market & 2nd","state":"waiting"}]},{"say":"Take Market & 1st from the queue. Warehouse 1 reaches it in 5, and nothing reaches it sooner.","ops":[{"v":"Market & 1st","state":"current"},{"panel":"queue","list":[{"key":"Main & 4th","note":"6"},{"key":"River & 3rd","note":"6"},{"key":"Pine & 4th","note":"7"},{"key":"Main & 3rd","note":"7"},{"key":"Market & 2nd","note":"7"},{"key":"Pine & 5th","note":"7"},{"key":"Market & 3rd","note":"7"}]},{"v":"Main & 2nd","state":"component-1"},{"panel":"areas","groups":[["Pine & 1st","Pine & 2nd","Main & 1st","Pine & 3rd","Main & 2nd","Market & 1st"],["River & 5th","Market & 5th","Main & 5th","Market & 4th","River & 4th"]]}]},{"say":"Market & 1st to Market & 2nd: 5 + 2 = 7, not quicker than 7, so Market & 2nd stays with warehouse 1.","ops":[{"e":["Market & 1st","Market & 2nd"],"state":"examined"}]},{"say":"Market & 1st to River & 1st: 5 + 2 = 7, so River & 1st goes to warehouse 1 at 7.","ops":[{"e":["Market & 1st","River & 1st"],"state":"area-1"},{"panel":"dist","set":{"River & 1st":"7"}},{"panel":"queue","list":[{"key":"Main & 4th","note":"6"},{"key":"River & 3rd","note":"6"},{"key":"Pine & 4th","note":"7"},{"key":"Main & 3rd","note":"7"},{"key":"Market & 2nd","note":"7"},{"key":"River & 1st","note":"7"},{"key":"Pine & 5th","note":"7"},{"key":"Market & 3rd","note":"7"}]},{"v":"River & 1st","state":"waiting"}]},{"say":"Take Main & 4th from the queue. Warehouse 2 reaches it in 6, and nothing reaches it sooner.","ops":[{"v":"Main & 4th","state":"current"},{"panel":"queue","list":[{"key":"River & 3rd","note":"6"},{"key":"Pine & 4th","note":"7"},{"key":"Main & 3rd","note":"7"},{"key":"Market & 2nd","note":"7"},{"key":"River & 1st","note":"7"},{"key":"Pine & 5th","note":"7"},{"key":"Market & 3rd","note":"7"}]},{"v":"Market & 1st","state":"component-1"},{"panel":"areas","groups":[["Pine & 1st","Pine & 2nd","Main & 1st","Pine & 3rd","Main & 2nd","Market & 1st"],["River & 5th","Market & 5th","Main & 5th","Market & 4th","River & 4th","Main & 4th"]]}]},{"say":"Main & 4th to Pine & 4th: 6 + 2 = 8, not quicker than 7, so Pine & 4th stays with warehouse 1.","ops":[{"e":["Main & 4th","Pine & 4th"],"state":"examined"}]},{"say":"Main & 4th to Main & 3rd: 6 + 4 = 10, not quicker than 7, so Main & 3rd stays with warehouse 1.","ops":[{"e":["Main & 4th","Main & 3rd"],"state":"examined"}]},{"say":"Take River & 3rd from the queue. Warehouse 2 reaches it in 6, and nothing reaches it sooner.","ops":[{"v":"River & 3rd","state":"current"},{"panel":"queue","list":[{"key":"Pine & 4th","note":"7"},{"key":"Main & 3rd","note":"7"},{"key":"Market & 2nd","note":"7"},{"key":"River & 1st","note":"7"},{"key":"Pine & 5th","note":"7"},{"key":"Market & 3rd","note":"7"}]},{"v":"Main & 4th","state":"component-2"},{"panel":"areas","groups":[["Pine & 1st","Pine & 2nd","Main & 1st","Pine & 3rd","Main & 2nd","Market & 1st"],["River & 5th","Market & 5th","Main & 5th","Market & 4th","River & 4th","Main & 4th","River & 3rd"]]}]},{"say":"River & 3rd to Market & 3rd: 6 + 3 = 9, not quicker than 7, so Market & 3rd stays with warehouse 2.","ops":[{"e":["River & 3rd","Market & 3rd"],"state":"examined"}]},{"say":"River & 3rd to River & 2nd: 6 + 2 = 8, so River & 2nd goes to warehouse 2 at 8.","ops":[{"e":["River & 3rd","River & 2nd"],"state":"area-2"},{"panel":"dist","set":{"River & 2nd":"8"}},{"panel":"queue","list":[{"key":"Pine & 4th","note":"7"},{"key":"Main & 3rd","note":"7"},{"key":"Market & 2nd","note":"7"},{"key":"River & 1st","note":"7"},{"key":"Pine & 5th","note":"7"},{"key":"Market & 3rd","note":"7"},{"key":"River & 2nd","note":"8"}]},{"v":"River & 2nd","state":"waiting"}]},{"say":"Take Pine & 4th from the queue. Warehouse 1 reaches it in 7, and nothing reaches it sooner.","ops":[{"v":"Pine & 4th","state":"current"},{"panel":"queue","list":[{"key":"Main & 3rd","note":"7"},{"key":"Market & 2nd","note":"7"},{"key":"River & 1st","note":"7"},{"key":"Pine & 5th","note":"7"},{"key":"Market & 3rd","note":"7"},{"key":"River & 2nd","note":"8"}]},{"v":"River & 3rd","state":"component-2"},{"panel":"areas","groups":[["Pine & 1st","Pine & 2nd","Main & 1st","Pine & 3rd","Main & 2nd","Market & 1st","Pine & 4th"],["River & 5th","Market & 5th","Main & 5th","Market & 4th","River & 4th","Main & 4th","River & 3rd"]]}]},{"say":"Pine & 4th to Pine & 5th: 7 + 3 = 10, not quicker than 7, so Pine & 5th stays with warehouse 2.","ops":[{"e":["Pine & 4th","Pine & 5th"],"state":"examined"}]},{"say":"Take Main & 3rd from the queue. Warehouse 1 reaches it in 7, and nothing reaches it sooner.","ops":[{"v":"Main & 3rd","state":"current"},{"panel":"queue","list":[{"key":"Market & 2nd","note":"7"},{"key":"River & 1st","note":"7"},{"key":"Pine & 5th","note":"7"},{"key":"Market & 3rd","note":"7"},{"key":"River & 2nd","note":"8"}]},{"v":"Pine & 4th","state":"component-1"},{"panel":"areas","groups":[["Pine & 1st","Pine & 2nd","Main & 1st","Pine & 3rd","Main & 2nd","Market & 1st","Pine & 4th","Main & 3rd"],["River & 5th","Market & 5th","Main & 5th","Market & 4th","River & 4th","Main & 4th","River & 3rd"]]}]},{"say":"Main & 3rd to Market & 3rd: 7 + 3 = 10, not quicker than 7, so Market & 3rd stays with warehouse 2.","ops":[{"e":["Main & 3rd","Market & 3rd"],"state":"examined"}]},{"say":"Take Market & 2nd from the queue. Warehouse 1 reaches it in 7, and nothing reaches it sooner.","ops":[{"v":"Market & 2nd","state":"current"},{"panel":"queue","list":[{"key":"River & 1st","note":"7"},{"key":"Pine & 5th","note":"7"},{"key":"Market & 3rd","note":"7"},{"key":"River & 2nd","note":"8"}]},{"v":"Main & 3rd","state":"component-1"},{"panel":"areas","groups":[["Pine & 1st","Pine & 2nd","Main & 1st","Pine & 3rd","Main & 2nd","Market & 1st","Pine & 4th","Main & 3rd","Market & 2nd"],["River & 5th","Market & 5th","Main & 5th","Market & 4th","River & 4th","Main & 4th","River & 3rd"]]}]},{"say":"Market & 2nd to River & 2nd: 7 + 2 = 9, not quicker than 8, so River & 2nd stays with warehouse 2.","ops":[{"e":["Market & 2nd","River & 2nd"],"state":"examined"}]},{"say":"Take River & 1st from the queue. Warehouse 1 reaches it in 7, and nothing reaches it sooner.","ops":[{"v":"River & 1st","state":"current"},{"panel":"queue","list":[{"key":"Pine & 5th","note":"7"},{"key":"Market & 3rd","note":"7"},{"key":"River & 2nd","note":"8"}]},{"v":"Market & 2nd","state":"component-1"},{"panel":"areas","groups":[["Pine & 1st","Pine & 2nd","Main & 1st","Pine & 3rd","Main & 2nd","Market & 1st","Pine & 4th","Main & 3rd","Market & 2nd","River & 1st"],["River & 5th","Market & 5th","Main & 5th","Market & 4th","River & 4th","Main & 4th","River & 3rd"]]}]},{"say":"River & 1st to River & 2nd: 7 + 3 = 10, not quicker than 8, so River & 2nd stays with warehouse 2.","ops":[{"e":["River & 1st","River & 2nd"],"state":"examined"}]},{"say":"Take Pine & 5th from the queue. Warehouse 2 reaches it in 7, and nothing reaches it sooner. It has no unsettled neighbors.","ops":[{"v":"Pine & 5th","state":"current"},{"panel":"queue","list":[{"key":"Market & 3rd","note":"7"},{"key":"River & 2nd","note":"8"}]},{"v":"River & 1st","state":"component-1"},{"panel":"areas","groups":[["Pine & 1st","Pine & 2nd","Main & 1st","Pine & 3rd","Main & 2nd","Market & 1st","Pine & 4th","Main & 3rd","Market & 2nd","River & 1st"],["River & 5th","Market & 5th","Main & 5th","Market & 4th","River & 4th","Main & 4th","River & 3rd","Pine & 5th"]]}]},{"say":"Take Market & 3rd from the queue. Warehouse 2 reaches it in 7, and nothing reaches it sooner. It has no unsettled neighbors.","ops":[{"v":"Market & 3rd","state":"current"},{"panel":"queue","list":[{"key":"River & 2nd","note":"8"}]},{"v":"Pine & 5th","state":"component-2"},{"panel":"areas","groups":[["Pine & 1st","Pine & 2nd","Main & 1st","Pine & 3rd","Main & 2nd","Market & 1st","Pine & 4th","Main & 3rd","Market & 2nd","River & 1st"],["River & 5th","Market & 5th","Main & 5th","Market & 4th","River & 4th","Main & 4th","River & 3rd","Pine & 5th","Market & 3rd"]]}]},{"say":"Take River & 2nd from the queue. Warehouse 2 reaches it in 8, and nothing reaches it sooner. It has no unsettled neighbors.","ops":[{"v":"River & 2nd","state":"current"},{"panel":"queue","list":[]},{"v":"Market & 3rd","state":"component-2"},{"panel":"areas","groups":[["Pine & 1st","Pine & 2nd","Main & 1st","Pine & 3rd","Main & 2nd","Market & 1st","Pine & 4th","Main & 3rd","Market & 2nd","River & 1st"],["River & 5th","Market & 5th","Main & 5th","Market & 4th","River & 4th","Main & 4th","River & 3rd","Pine & 5th","Market & 3rd","River & 2nd"]]}]},{"say":"Done. Every place has its nearest warehouse. One search settled 20 places. path.Dijkstra from each warehouse in turn would settle 40 between them.","ops":[{"panel":"areas","groups":[["Pine & 1st","Pine & 2nd","Main & 1st","Pine & 3rd","Main & 2nd","Market & 1st","Pine & 4th","Main & 3rd","Market & 2nd","River & 1st"],["River & 5th","Market & 5th","Main & 5th","Market & 4th","River & 4th","Main & 4th","River & 3rd","Pine & 5th","Market & 3rd","River & 2nd"]]},{"v":"River & 2nd","state":"component-2"}]}],"traceNote":"","verification":"The steps come from a step-by-step copy of the algorithm. Its result is checked against gograph's on every start.","snippet":"nearest, err := path.DijkstraMultiSource(g, \"Pine & 1st\", \"River & 5th\")\nif err != nil {\n\treturn err\n}\nfor _, v := range g.GetAllVertices() {\n\tfrom, ok := nearest.Source(v.Label())\n\tif !ok {\n\t\tcontinue\n\t}\n\tminutes, _ := nearest.Distance(v.Label())\n\tfmt.Println(v.Label(), from.Label(), minutes)\n}"}