{"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":"delivery-area","name":"Delivery area","description":"Eight stops in a small town. Streets are one way, and each edge is the travel time in minutes.","family":"road","directed":true,"weighted":true,"acyclic":false,"vertices":[{"id":"Depot","x":128,"y":320},{"id":"Bakery","x":352,"y":128},{"id":"Market","x":352,"y":512},{"id":"School","x":608,"y":128},{"id":"Park","x":608,"y":352},{"id":"Clinic","x":608,"y":544},{"id":"Library","x":832,"y":224},{"id":"Station","x":864,"y":480}],"edges":[{"from":"Depot","to":"Bakery","weight":4},{"from":"Depot","to":"Market","weight":2},{"from":"Market","to":"Bakery","weight":1},{"from":"Bakery","to":"School","weight":5},{"from":"Bakery","to":"Park","weight":7},{"from":"Market","to":"Park","weight":8},{"from":"Market","to":"Clinic","weight":10},{"from":"School","to":"Library","weight":3},{"from":"Park","to":"Library","weight":2},{"from":"Park","to":"Station","weight":6},{"from":"Clinic","to":"Station","weight":2},{"from":"Library","to":"Station","weight":5}],"details":{"vertices":8,"edges":12,"directed":true,"weighted":true,"acyclic":true,"weightMin":1,"weightMax":10,"negativeWeights":false,"density":0.21428571428571427,"inDegree":{"min":0,"avg":1.5,"max":3},"outDegree":{"min":0,"avg":1.5,"max":3},"selfLoops":0,"components":1}},"problem":"With a second depot at the park, which depot should deliver to each stop, and what is the longest drive?","params":{"sources":["Depot","Park"]},"result":{"kind":"groups","groups":[["Bakery","Clinic","Depot","Market","School"],["Library","Park","Station"]]},"answer":"Warehouse 1 at Depot serves 5 and 2 at Park serves 3. The longest drive is 12, from warehouse 1 to Clinic.","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 5","color":"#009E73","shape":"filled"},{"id":"component-2","label":"Warehouse 2, serves 3","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 Depot and 2 at Park. Each place goes to the warehouse that can reach it soonest, so one search serves them all.","ops":[{"panel":"dist","set":{"Depot":"∞"}},{"panel":"dist","set":{"Bakery":"∞"}},{"panel":"dist","set":{"Market":"∞"}},{"panel":"dist","set":{"School":"∞"}},{"panel":"dist","set":{"Park":"∞"}},{"panel":"dist","set":{"Clinic":"∞"}},{"panel":"dist","set":{"Library":"∞"}},{"panel":"dist","set":{"Station":"∞"}},{"v":"Depot","state":"waiting"},{"panel":"dist","set":{"Depot":"0"}},{"v":"Park","state":"waiting"},{"panel":"dist","set":{"Park":"0"}},{"panel":"queue","list":[{"key":"Depot","note":"0"},{"key":"Park","note":"0"}]}]},{"say":"Take Depot from the queue. It is warehouse 1, at 0 from itself.","ops":[{"v":"Depot","state":"current"},{"panel":"queue","list":[{"key":"Park","note":"0"}]},{"panel":"areas","groups":[["Depot"]]}]},{"say":"Depot to Bakery: 0 + 4 = 4, so Bakery goes to warehouse 1 at 4.","ops":[{"e":["Depot","Bakery"],"state":"area-1"},{"panel":"dist","set":{"Bakery":"4"}},{"panel":"queue","list":[{"key":"Park","note":"0"},{"key":"Bakery","note":"4"}]},{"v":"Bakery","state":"waiting"}]},{"say":"Depot to Market: 0 + 2 = 2, so Market goes to warehouse 1 at 2.","ops":[{"e":["Depot","Market"],"state":"area-1"},{"panel":"dist","set":{"Market":"2"}},{"panel":"queue","list":[{"key":"Park","note":"0"},{"key":"Market","note":"2"},{"key":"Bakery","note":"4"}]},{"v":"Market","state":"waiting"}]},{"say":"Take Park from the queue. It is warehouse 2, at 0 from itself.","ops":[{"v":"Park","state":"current"},{"panel":"queue","list":[{"key":"Market","note":"2"},{"key":"Bakery","note":"4"}]},{"v":"Depot","state":"component-1"},{"panel":"areas","groups":[["Depot"],["Park"]]}]},{"say":"Park to Library: 0 + 2 = 2, so Library goes to warehouse 2 at 2.","ops":[{"e":["Park","Library"],"state":"area-2"},{"panel":"dist","set":{"Library":"2"}},{"panel":"queue","list":[{"key":"Market","note":"2"},{"key":"Library","note":"2"},{"key":"Bakery","note":"4"}]},{"v":"Library","state":"waiting"}]},{"say":"Park to Station: 0 + 6 = 6, so Station goes to warehouse 2 at 6.","ops":[{"e":["Park","Station"],"state":"area-2"},{"panel":"dist","set":{"Station":"6"}},{"panel":"queue","list":[{"key":"Market","note":"2"},{"key":"Library","note":"2"},{"key":"Bakery","note":"4"},{"key":"Station","note":"6"}]},{"v":"Station","state":"waiting"}]},{"say":"Take Market from the queue. Warehouse 1 reaches it in 2, and nothing reaches it sooner.","ops":[{"v":"Market","state":"current"},{"panel":"queue","list":[{"key":"Library","note":"2"},{"key":"Bakery","note":"4"},{"key":"Station","note":"6"}]},{"v":"Park","state":"component-2"},{"panel":"areas","groups":[["Depot","Market"],["Park"]]}]},{"say":"Market to Bakery: 2 + 1 = 3, quicker than 4 from warehouse 1, so Bakery goes to warehouse 1 at 3.","ops":[{"e":["Market","Bakery"],"state":"area-1"},{"panel":"dist","set":{"Bakery":"3"}},{"panel":"queue","list":[{"key":"Library","note":"2"},{"key":"Bakery","note":"3"},{"key":"Station","note":"6"}]},{"e":["Depot","Bakery"],"state":"examined"}]},{"say":"Market to Clinic: 2 + 10 = 12, so Clinic goes to warehouse 1 at 12.","ops":[{"e":["Market","Clinic"],"state":"area-1"},{"panel":"dist","set":{"Clinic":"12"}},{"panel":"queue","list":[{"key":"Library","note":"2"},{"key":"Bakery","note":"3"},{"key":"Station","note":"6"},{"key":"Clinic","note":"12"}]},{"v":"Clinic","state":"waiting"}]},{"say":"Take Library from the queue. Warehouse 2 reaches it in 2, and nothing reaches it sooner.","ops":[{"v":"Library","state":"current"},{"panel":"queue","list":[{"key":"Bakery","note":"3"},{"key":"Station","note":"6"},{"key":"Clinic","note":"12"}]},{"v":"Market","state":"component-1"},{"panel":"areas","groups":[["Depot","Market"],["Park","Library"]]}]},{"say":"Library to Station: 2 + 5 = 7, not quicker than 6, so Station stays with warehouse 2.","ops":[{"e":["Library","Station"],"state":"examined"}]},{"say":"Take Bakery from the queue. Warehouse 1 reaches it in 3, and nothing reaches it sooner.","ops":[{"v":"Bakery","state":"current"},{"panel":"queue","list":[{"key":"Station","note":"6"},{"key":"Clinic","note":"12"}]},{"v":"Library","state":"component-2"},{"panel":"areas","groups":[["Depot","Market","Bakery"],["Park","Library"]]}]},{"say":"Bakery to School: 3 + 5 = 8, so School goes to warehouse 1 at 8.","ops":[{"e":["Bakery","School"],"state":"area-1"},{"panel":"dist","set":{"School":"8"}},{"panel":"queue","list":[{"key":"Station","note":"6"},{"key":"School","note":"8"},{"key":"Clinic","note":"12"}]},{"v":"School","state":"waiting"}]},{"say":"Take Station from the queue. Warehouse 2 reaches it in 6, and nothing reaches it sooner. It has no unsettled neighbors.","ops":[{"v":"Station","state":"current"},{"panel":"queue","list":[{"key":"School","note":"8"},{"key":"Clinic","note":"12"}]},{"v":"Bakery","state":"component-1"},{"panel":"areas","groups":[["Depot","Market","Bakery"],["Park","Library","Station"]]}]},{"say":"Take School from the queue. Warehouse 1 reaches it in 8, and nothing reaches it sooner. It has no unsettled neighbors.","ops":[{"v":"School","state":"current"},{"panel":"queue","list":[{"key":"Clinic","note":"12"}]},{"v":"Station","state":"component-2"},{"panel":"areas","groups":[["Depot","Market","Bakery","School"],["Park","Library","Station"]]}]},{"say":"Take Clinic from the queue. Warehouse 1 reaches it in 12, and nothing reaches it sooner. It has no unsettled neighbors.","ops":[{"v":"Clinic","state":"current"},{"panel":"queue","list":[]},{"v":"School","state":"component-1"},{"panel":"areas","groups":[["Depot","Market","Bakery","School","Clinic"],["Park","Library","Station"]]}]},{"say":"Done. Every place has its nearest warehouse. One search settled 8 places. path.Dijkstra from each warehouse in turn would settle 11 between them.","ops":[{"panel":"areas","groups":[["Depot","Market","Bakery","School","Clinic"],["Park","Library","Station"]]},{"v":"Clinic","state":"component-1"}]}],"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, \"Depot\", \"Park\")\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}"}