{"algorithm":"bellman-ford","about":["Bellman-Ford starts like Dijkstra, with 0 at the start and infinity everywhere else, but it doesn't take vertices in order of distance. It goes through every edge, and when an edge gives its end a shorter distance, it lowers that distance. It repeats this pass one time fewer than there are vertices. A shortest path that doesn't repeat a vertex has at most that many edges, so after the last pass every distance is final.","Then it makes one more pass. If an edge can still shorten a distance, the start can reach a cycle whose weights add up to less than zero. Such a graph has no shortest path, since each trip around the cycle makes the path shorter, and path.BellmanFordPaths returns ErrNegativeWeightCycle. It needs a directed, weighted graph and costs O(V·E). path.NegativeCycle then returns one such cycle. It searches the whole graph rather than what one start reaches, so on a graph with more than one it can return a cycle other than the one the start runs into.","When there is no negative cycle, Distance and PathTo on the result give each distance and the route there, start first, and report false for a vertex out of reach. Of two routes that are equally short, PathTo returns the one with the fewest edges.","Use it when some weights are negative, such as refunds, rewards or the negative logarithms of exchange rates, where a negative cycle is a chance for arbitrage. When no weight is negative, Dijkstra gives the same distances faster."],"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":"How many minutes is the quickest drive from the depot to each stop?","params":{"start":"Depot"},"result":{"kind":"distances","values":{"Bakery":3,"Clinic":12,"Depot":0,"Library":11,"Market":2,"Park":10,"School":8,"Station":14}},"answer":"From Depot, the shortest distances are 2 to Market, 3 to Bakery, 8 to School, 10 to Park, 11 to Library, 12 to Clinic and 14 to Station.","legend":{"vertex":[{"id":"idle","label":"Not reached","color":"#64748B","shape":"hollow"},{"id":"waiting","label":"Changed in this pass","color":"#E69F00","shape":"dashed-square"},{"id":"current","label":"Latest change","color":"#56B4E9","shape":"ring"},{"id":"done","label":"Reached","color":"#009E73","shape":"filled"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"tree","label":"Best way in so far","color":"#009E73","shape":"thick"},{"id":"error","label":"Negative cycle","color":"#D55E00","shape":"dashed"}],"panels":[{"id":"dist","title":"Distances","kind":"table"},{"id":"changed","title":"Changed in this pass","kind":"list"}]},"steps":[{"say":"Every distance starts at ∞, except Depot, which is 0. Bellman-Ford checks all 12 edges in each of 7 passes, one fewer than the 8 vertices, then once more to look for a negative cycle.","ops":[{"v":"Depot","state":"done"},{"panel":"dist","set":{"Depot":"0"}},{"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":"∞"}}]},{"say":"Pass 1. Depot to Bakery: 0 + 4 = 4, so Bakery's distance becomes 4.","ops":[{"v":"Bakery","state":"current"},{"e":["Depot","Bakery"],"state":"tree"},{"panel":"dist","set":{"Bakery":"4"}},{"panel":"changed","list":[{"key":"Bakery","note":"4"}]}]},{"say":"Pass 1. Depot to Market: 0 + 2 = 2, so Market's distance becomes 2.","ops":[{"v":"Market","state":"current"},{"e":["Depot","Market"],"state":"tree"},{"panel":"dist","set":{"Market":"2"}},{"panel":"changed","list":[{"key":"Bakery","note":"4"},{"key":"Market","note":"2"}]},{"v":"Bakery","state":"waiting"}]},{"say":"Pass 1. Bakery to School: 4 + 5 = 9, so School's distance becomes 9.","ops":[{"v":"School","state":"current"},{"e":["Bakery","School"],"state":"tree"},{"panel":"dist","set":{"School":"9"}},{"panel":"changed","list":[{"key":"Bakery","note":"4"},{"key":"Market","note":"2"},{"key":"School","note":"9"}]},{"v":"Market","state":"waiting"}]},{"say":"Pass 1. Bakery to Park: 4 + 7 = 11, so Park's distance becomes 11.","ops":[{"v":"Park","state":"current"},{"e":["Bakery","Park"],"state":"tree"},{"panel":"dist","set":{"Park":"11"}},{"panel":"changed","list":[{"key":"Bakery","note":"4"},{"key":"Market","note":"2"},{"key":"School","note":"9"},{"key":"Park","note":"11"}]},{"v":"School","state":"waiting"}]},{"say":"Pass 1. Market to Bakery: 2 + 1 = 3, shorter than 4, so Bakery's distance becomes 3.","ops":[{"v":"Bakery","state":"current"},{"e":["Market","Bakery"],"state":"tree"},{"panel":"dist","set":{"Bakery":"3"}},{"panel":"changed","list":[{"key":"Bakery","note":"3"},{"key":"Market","note":"2"},{"key":"School","note":"9"},{"key":"Park","note":"11"}]},{"e":["Depot","Bakery"],"state":"idle"},{"v":"Park","state":"waiting"}]},{"say":"Pass 1. Market to Park: 2 + 8 = 10, shorter than 11, so Park's distance becomes 10.","ops":[{"v":"Park","state":"current"},{"e":["Market","Park"],"state":"tree"},{"panel":"dist","set":{"Park":"10"}},{"panel":"changed","list":[{"key":"Bakery","note":"3"},{"key":"Market","note":"2"},{"key":"School","note":"9"},{"key":"Park","note":"10"}]},{"e":["Bakery","Park"],"state":"idle"},{"v":"Bakery","state":"waiting"}]},{"say":"Pass 1. Market to Clinic: 2 + 10 = 12, so Clinic's distance becomes 12.","ops":[{"v":"Clinic","state":"current"},{"e":["Market","Clinic"],"state":"tree"},{"panel":"dist","set":{"Clinic":"12"}},{"panel":"changed","list":[{"key":"Bakery","note":"3"},{"key":"Market","note":"2"},{"key":"School","note":"9"},{"key":"Park","note":"10"},{"key":"Clinic","note":"12"}]},{"v":"Park","state":"waiting"}]},{"say":"Pass 1. School to Library: 9 + 3 = 12, so Library's distance becomes 12.","ops":[{"v":"Library","state":"current"},{"e":["School","Library"],"state":"tree"},{"panel":"dist","set":{"Library":"12"}},{"panel":"changed","list":[{"key":"Bakery","note":"3"},{"key":"Market","note":"2"},{"key":"School","note":"9"},{"key":"Park","note":"10"},{"key":"Clinic","note":"12"},{"key":"Library","note":"12"}]},{"v":"Clinic","state":"waiting"}]},{"say":"Pass 1. Park to Station: 10 + 6 = 16, so Station's distance becomes 16.","ops":[{"v":"Station","state":"current"},{"e":["Park","Station"],"state":"tree"},{"panel":"dist","set":{"Station":"16"}},{"panel":"changed","list":[{"key":"Bakery","note":"3"},{"key":"Market","note":"2"},{"key":"School","note":"9"},{"key":"Park","note":"10"},{"key":"Clinic","note":"12"},{"key":"Library","note":"12"},{"key":"Station","note":"16"}]},{"v":"Library","state":"waiting"}]},{"say":"Pass 1. Clinic to Station: 12 + 2 = 14, shorter than 16, so Station's distance becomes 14.","ops":[{"v":"Station","state":"current"},{"e":["Clinic","Station"],"state":"tree"},{"panel":"dist","set":{"Station":"14"}},{"panel":"changed","list":[{"key":"Bakery","note":"3"},{"key":"Market","note":"2"},{"key":"School","note":"9"},{"key":"Park","note":"10"},{"key":"Clinic","note":"12"},{"key":"Library","note":"12"},{"key":"Station","note":"14"}]},{"e":["Park","Station"],"state":"idle"}]},{"say":"Pass 1 done. 7 distances changed.","ops":[{"v":"Bakery","state":"done"},{"v":"Market","state":"done"},{"v":"School","state":"done"},{"v":"Park","state":"done"},{"v":"Clinic","state":"done"},{"v":"Library","state":"done"},{"v":"Station","state":"done"}]},{"say":"Pass 2. Bakery to School: 3 + 5 = 8, shorter than 9, so School's distance becomes 8.","ops":[{"v":"School","state":"current"},{"e":["Bakery","School"],"state":"tree"},{"panel":"dist","set":{"School":"8"}},{"panel":"changed","list":[{"key":"School","note":"8"}]}]},{"say":"Pass 2. School to Library: 8 + 3 = 11, shorter than 12, so Library's distance becomes 11.","ops":[{"v":"Library","state":"current"},{"e":["School","Library"],"state":"tree"},{"panel":"dist","set":{"Library":"11"}},{"panel":"changed","list":[{"key":"School","note":"8"},{"key":"Library","note":"11"}]},{"v":"School","state":"waiting"}]},{"say":"Pass 2 done. The distances of School and Library changed.","ops":[{"v":"School","state":"done"},{"v":"Library","state":"done"}]},{"say":"Pass 3 done. No distance changed, so later passes won't change any either, but gograph runs them all.","ops":[{"panel":"changed","list":[]}]},{"say":"Pass 4 done. No distance changed."},{"say":"Pass 5 done. No distance changed."},{"say":"Pass 6 done. No distance changed."},{"say":"Pass 7 done. No distance changed."},{"say":"Extra pass. No edge gives a shorter distance, so there is no negative cycle. Every distance from Depot is final."}],"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.BellmanFordPaths on every start. Of two routes that are equally short, BellmanFordPaths takes the one with the fewest edges, and the steps keep the last edge that lowered each distance, so the drawn route can be another one as short. On a negative cycle, path.NegativeCycle searches the whole graph, so the check takes any loop whose weights add up to less than zero.","snippet":"paths, err := path.BellmanFordPaths(g, \"Depot\")\nif errors.Is(err, path.ErrNegativeWeightCycle) {\n\tloop, _ := path.NegativeCycle(g)\n\tfor _, v := range loop {\n\t\tfmt.Println(v.Label())\n\t}\n\treturn err\n}\nif err != nil {\n\treturn err\n}\ndist, ok := paths.Distance(\"Station\")\nif !ok {\n\treturn nil // out of reach\n}\nroute, _ := paths.PathTo(\"Station\")\nfmt.Println(dist)\nfor _, v := range route {\n\tfmt.Println(v.Label())\n}"}
