{"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":"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":"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 I23, which is 0. Bellman-Ford checks all 88 edges in each of 44 passes, one fewer than the 45 vertices, then once more to look for a negative cycle.","ops":[{"v":"I23","state":"done"},{"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":"∞"}}]},{"say":"Pass 1. I23 to I14: 0 + 3 = 3, so I14's distance becomes 3.","ops":[{"v":"I14","state":"current"},{"e":["I23","I14"],"state":"tree"},{"panel":"dist","set":{"I14":"3"}},{"panel":"changed","list":[{"key":"I14","note":"3"}]}]},{"say":"Pass 1. I23 to I22: 0 + 5 = 5, so I22's distance becomes 5.","ops":[{"v":"I22","state":"current"},{"e":["I23","I22"],"state":"tree"},{"panel":"dist","set":{"I22":"5"}},{"panel":"changed","list":[{"key":"I14","note":"3"},{"key":"I22","note":"5"}]},{"v":"I14","state":"waiting"}]},{"say":"Pass 1. I23 to I24: 0 + 5 = 5, so I24's distance becomes 5.","ops":[{"v":"I24","state":"current"},{"e":["I23","I24"],"state":"tree"},{"panel":"dist","set":{"I24":"5"}},{"panel":"changed","list":[{"key":"I14","note":"3"},{"key":"I22","note":"5"},{"key":"I24","note":"5"}]},{"v":"I22","state":"waiting"}]},{"say":"Pass 1. I23 to I32: 0 + 5 = 5, so I32's distance becomes 5.","ops":[{"v":"I32","state":"current"},{"e":["I23","I32"],"state":"tree"},{"panel":"dist","set":{"I32":"5"}},{"panel":"changed","list":[{"key":"I14","note":"3"},{"key":"I22","note":"5"},{"key":"I24","note":"5"},{"key":"I32","note":"5"}]},{"v":"I24","state":"waiting"}]},{"say":"Pass 1. I24 to I15: 5 + 4 = 9, so I15's distance becomes 9.","ops":[{"v":"I15","state":"current"},{"e":["I24","I15"],"state":"tree"},{"panel":"dist","set":{"I15":"9"}},{"panel":"changed","list":[{"key":"I14","note":"3"},{"key":"I22","note":"5"},{"key":"I24","note":"5"},{"key":"I32","note":"5"},{"key":"I15","note":"9"}]},{"v":"I32","state":"waiting"}]},{"say":"Pass 1. I24 to I25: 5 + 2 = 7, so I25's distance becomes 7.","ops":[{"v":"I25","state":"current"},{"e":["I24","I25"],"state":"tree"},{"panel":"dist","set":{"I25":"7"}},{"panel":"changed","list":[{"key":"I14","note":"3"},{"key":"I22","note":"5"},{"key":"I24","note":"5"},{"key":"I32","note":"5"},{"key":"I15","note":"9"},{"key":"I25","note":"7"}]},{"v":"I15","state":"waiting"}]},{"say":"Pass 1. I25 to I26: 7 + 4 = 11, so I26's distance becomes 11.","ops":[{"v":"I26","state":"current"},{"e":["I25","I26"],"state":"tree"},{"panel":"dist","set":{"I26":"11"}},{"panel":"changed","list":[{"key":"I14","note":"3"},{"key":"I22","note":"5"},{"key":"I24","note":"5"},{"key":"I32","note":"5"},{"key":"I15","note":"9"},{"key":"I25","note":"7"},{"key":"I26","note":"11"}]},{"v":"I25","state":"waiting"}]},{"say":"Pass 1. I25 to I34: 7 + 3 = 10, so I34's distance becomes 10.","ops":[{"v":"I34","state":"current"},{"e":["I25","I34"],"state":"tree"},{"panel":"dist","set":{"I34":"10"}},{"panel":"changed","list":[{"key":"I14","note":"3"},{"key":"I22","note":"5"},{"key":"I24","note":"5"},{"key":"I32","note":"5"},{"key":"I15","note":"9"},{"key":"I25","note":"7"},{"key":"I26","note":"11"},{"key":"I34","note":"10"}]},{"v":"I26","state":"waiting"}]},{"say":"Pass 1. I26 to I17: 11 + 4 = 15, so I17's distance becomes 15.","ops":[{"v":"I17","state":"current"},{"e":["I26","I17"],"state":"tree"},{"panel":"dist","set":{"I17":"15"}},{"panel":"changed","list":[{"key":"I14","note":"3"},{"key":"I22","note":"5"},{"key":"I24","note":"5"},{"key":"I32","note":"5"},{"key":"I15","note":"9"},{"key":"I25","note":"7"},{"key":"I26","note":"11"},{"key":"I34","note":"10"},{"key":"I17","note":"15"}]},{"v":"I34","state":"waiting"}]},{"say":"Pass 1. I26 to I27: 11 + 5 = 16, so I27's distance becomes 16.","ops":[{"v":"I27","state":"current"},{"e":["I26","I27"],"state":"tree"},{"panel":"dist","set":{"I27":"16"}},{"panel":"changed","list":[{"key":"I14","note":"3"},{"key":"I22","note":"5"},{"key":"I24","note":"5"},{"key":"I32","note":"5"},{"key":"I15","note":"9"},{"key":"I25","note":"7"},{"key":"I26","note":"11"},{"key":"I34","note":"10"},{"key":"I17","note":"15"},{"key":"I27","note":"16"}]},{"v":"I17","state":"waiting"}]},{"say":"Pass 1. I27 to I36: 16 + 3 = 19, so I36's distance becomes 19.","ops":[{"v":"I36","state":"current"},{"e":["I27","I36"],"state":"tree"},{"panel":"dist","set":{"I36":"19"}},{"panel":"changed","list":[{"key":"I14","note":"3"},{"key":"I22","note":"5"},{"key":"I24","note":"5"},{"key":"I32","note":"5"},{"key":"I15","note":"9"},{"key":"I25","note":"7"},{"key":"I26","note":"11"},{"key":"I34","note":"10"},{"key":"I17","note":"15"},{"key":"I27","note":"16"},{"key":"I36","note":"19"}]},{"v":"I27","state":"waiting"}]},{"say":"Pass 1. I32 to I33: 5 + 5 = 10, so I33's distance becomes 10.","ops":[{"v":"I33","state":"current"},{"e":["I32","I33"],"state":"tree"},{"panel":"dist","set":{"I33":"10"}},{"panel":"changed","list":[{"key":"I14","note":"3"},{"key":"I22","note":"5"},{"key":"I24","note":"5"},{"key":"I32","note":"5"},{"key":"I15","note":"9"},{"key":"I25","note":"7"},{"key":"I26","note":"11"},{"key":"I34","note":"10"},{"key":"I17","note":"15"},{"key":"I27","note":"16"},{"key":"I36","note":"19"},{"key":"I33","note":"10"}]},{"v":"I36","state":"waiting"}]},{"say":"Pass 1. I32 to I41: 5 + 4 = 9, so I41's distance becomes 9.","ops":[{"v":"I41","state":"current"},{"e":["I32","I41"],"state":"tree"},{"panel":"dist","set":{"I41":"9"}},{"panel":"changed","list":[{"key":"I14","note":"3"},{"key":"I22","note":"5"},{"key":"I24","note":"5"},{"key":"I32","note":"5"},{"key":"I15","note":"9"},{"key":"I25","note":"7"},{"key":"I26","note":"11"},{"key":"I34","note":"10"},{"key":"I17","note":"15"},{"key":"I27","note":"16"},{"key":"I36","note":"19"},{"key":"I33","note":"10"},{"key":"I41","note":"9"}]},{"v":"I33","state":"waiting"}]},{"say":"Pass 1. I34 to I35: 10 + 5 = 15, so I35's distance becomes 15.","ops":[{"v":"I35","state":"current"},{"e":["I34","I35"],"state":"tree"},{"panel":"dist","set":{"I35":"15"}},{"panel":"changed","list":[{"key":"I14","note":"3"},{"key":"I22","note":"5"},{"key":"I24","note":"5"},{"key":"I32","note":"5"},{"key":"I15","note":"9"},{"key":"I25","note":"7"},{"key":"I26","note":"11"},{"key":"I34","note":"10"},{"key":"I17","note":"15"},{"key":"I27","note":"16"},{"key":"I36","note":"19"},{"key":"I33","note":"10"},{"key":"I41","note":"9"},{"key":"I35","note":"15"}]},{"v":"I41","state":"waiting"}]},{"say":"Pass 1. I34 to I43: 10 + 3 = 13, so I43's distance becomes 13.","ops":[{"v":"I43","state":"current"},{"e":["I34","I43"],"state":"tree"},{"panel":"dist","set":{"I43":"13"}},{"panel":"changed","list":[{"key":"I14","note":"3"},{"key":"I22","note":"5"},{"key":"I24","note":"5"},{"key":"I32","note":"5"},{"key":"I15","note":"9"},{"key":"I25","note":"7"},{"key":"I26","note":"11"},{"key":"I34","note":"10"},{"key":"I17","note":"15"},{"key":"I27","note":"16"},{"key":"I36","note":"19"},{"key":"I33","note":"10"},{"key":"I41","note":"9"},{"key":"I35","note":"15"},{"key":"I43","note":"13"}]},{"v":"I35","state":"waiting"}]},{"say":"Pass 1. I36 to I45: 19 + 2 = 21, so I45's distance becomes 21.","ops":[{"v":"I45","state":"current"},{"e":["I36","I45"],"state":"tree"},{"panel":"dist","set":{"I45":"21"}},{"panel":"changed","list":[{"key":"I14","note":"3"},{"key":"I22","note":"5"},{"key":"I24","note":"5"},{"key":"I32","note":"5"},{"key":"I15","note":"9"},{"key":"I25","note":"7"},{"key":"I26","note":"11"},{"key":"I34","note":"10"},{"key":"I17","note":"15"},{"key":"I27","note":"16"},{"key":"I36","note":"19"},{"key":"I33","note":"10"},{"key":"I41","note":"9"},{"key":"I35","note":"15"},{"key":"I43","note":"13"},{"key":"I45","note":"21"}]},{"v":"I43","state":"waiting"}]},{"say":"Pass 1. I41 to I40: 9 + 2 = 11, so I40's distance becomes 11.","ops":[{"v":"I40","state":"current"},{"e":["I41","I40"],"state":"tree"},{"panel":"dist","set":{"I40":"11"}},{"panel":"changed","list":[{"key":"I14","note":"3"},{"key":"I22","note":"5"},{"key":"I24","note":"5"},{"key":"I32","note":"5"},{"key":"I15","note":"9"},{"key":"I25","note":"7"},{"key":"I26","note":"11"},{"key":"I34","note":"10"},{"key":"I17","note":"15"},{"key":"I27","note":"16"},{"key":"I36","note":"19"},{"key":"I33","note":"10"},{"key":"I41","note":"9"},{"key":"I35","note":"15"},{"key":"I43","note":"13"},{"key":"I45","note":"21"},{"key":"I40","note":"11"}]},{"v":"I45","state":"waiting"}]},{"say":"Pass 1. I43 to I42: 13 + 3 = 16, so I42's distance becomes 16.","ops":[{"v":"I42","state":"current"},{"e":["I43","I42"],"state":"tree"},{"panel":"dist","set":{"I42":"16"}},{"panel":"changed","list":[{"key":"I14","note":"3"},{"key":"I22","note":"5"},{"key":"I24","note":"5"},{"key":"I32","note":"5"},{"key":"I15","note":"9"},{"key":"I25","note":"7"},{"key":"I26","note":"11"},{"key":"I34","note":"10"},{"key":"I17","note":"15"},{"key":"I27","note":"16"},{"key":"I36","note":"19"},{"key":"I33","note":"10"},{"key":"I41","note":"9"},{"key":"I35","note":"15"},{"key":"I43","note":"13"},{"key":"I45","note":"21"},{"key":"I40","note":"11"},{"key":"I42","note":"16"}]},{"v":"I40","state":"waiting"}]},{"say":"Pass 1. I45 to I44: 21 + 3 = 24, so I44's distance becomes 24.","ops":[{"v":"I44","state":"current"},{"e":["I45","I44"],"state":"tree"},{"panel":"dist","set":{"I44":"24"}},{"panel":"changed","list":[{"key":"I14","note":"3"},{"key":"I22","note":"5"},{"key":"I24","note":"5"},{"key":"I32","note":"5"},{"key":"I15","note":"9"},{"key":"I25","note":"7"},{"key":"I26","note":"11"},{"key":"I34","note":"10"},{"key":"I17","note":"15"},{"key":"I27","note":"16"},{"key":"I36","note":"19"},{"key":"I33","note":"10"},{"key":"I41","note":"9"},{"key":"I35","note":"15"},{"key":"I43","note":"13"},{"key":"I45","note":"21"},{"key":"I40","note":"11"},{"key":"I42","note":"16"},{"key":"I44","note":"24"}]},{"v":"I42","state":"waiting"}]},{"say":"Pass 1 done. 19 distances changed.","ops":[{"v":"I14","state":"done"},{"v":"I22","state":"done"},{"v":"I24","state":"done"},{"v":"I32","state":"done"},{"v":"I15","state":"done"},{"v":"I25","state":"done"},{"v":"I26","state":"done"},{"v":"I34","state":"done"},{"v":"I17","state":"done"},{"v":"I27","state":"done"},{"v":"I36","state":"done"},{"v":"I33","state":"done"},{"v":"I41","state":"done"},{"v":"I35","state":"done"},{"v":"I43","state":"done"},{"v":"I45","state":"done"},{"v":"I40","state":"done"},{"v":"I42","state":"done"},{"v":"I44","state":"done"}]},{"say":"Pass 2. I14 to I5: 3 + 5 = 8, so I5's distance becomes 8.","ops":[{"v":"I5","state":"current"},{"e":["I14","I5"],"state":"tree"},{"panel":"dist","set":{"I5":"8"}},{"panel":"changed","list":[{"key":"I5","note":"8"}]}]},{"say":"Pass 2. I14 to I13: 3 + 4 = 7, so I13's distance becomes 7.","ops":[{"v":"I13","state":"current"},{"e":["I14","I13"],"state":"tree"},{"panel":"dist","set":{"I13":"7"}},{"panel":"changed","list":[{"key":"I5","note":"8"},{"key":"I13","note":"7"}]},{"v":"I5","state":"waiting"}]},{"say":"Pass 2. I15 to I6: 9 + 4 = 13, so I6's distance becomes 13.","ops":[{"v":"I6","state":"current"},{"e":["I15","I6"],"state":"tree"},{"panel":"dist","set":{"I6":"13"}},{"panel":"changed","list":[{"key":"I5","note":"8"},{"key":"I13","note":"7"},{"key":"I6","note":"13"}]},{"v":"I13","state":"waiting"}]},{"say":"Pass 2. I17 to I8: 15 + 5 = 20, so I8's distance becomes 20.","ops":[{"v":"I8","state":"current"},{"e":["I17","I8"],"state":"tree"},{"panel":"dist","set":{"I8":"20"}},{"panel":"changed","list":[{"key":"I5","note":"8"},{"key":"I13","note":"7"},{"key":"I6","note":"13"},{"key":"I8","note":"20"}]},{"v":"I6","state":"waiting"}]},{"say":"Pass 2. I17 to I16: 15 + 2 = 17, so I16's distance becomes 17.","ops":[{"v":"I16","state":"current"},{"e":["I17","I16"],"state":"tree"},{"panel":"dist","set":{"I16":"17"}},{"panel":"changed","list":[{"key":"I5","note":"8"},{"key":"I13","note":"7"},{"key":"I6","note":"13"},{"key":"I8","note":"20"},{"key":"I16","note":"17"}]},{"v":"I8","state":"waiting"}]},{"say":"Pass 2. I22 to I21: 5 + 3 = 8, so I21's distance becomes 8.","ops":[{"v":"I21","state":"current"},{"e":["I22","I21"],"state":"tree"},{"panel":"dist","set":{"I21":"8"}},{"panel":"changed","list":[{"key":"I5","note":"8"},{"key":"I13","note":"7"},{"key":"I6","note":"13"},{"key":"I8","note":"20"},{"key":"I16","note":"17"},{"key":"I21","note":"8"}]},{"v":"I16","state":"waiting"}]},{"say":"Pass 2. I22 to I31: 5 + 2 = 7, so I31's distance becomes 7.","ops":[{"v":"I31","state":"current"},{"e":["I22","I31"],"state":"tree"},{"panel":"dist","set":{"I31":"7"}},{"panel":"changed","list":[{"key":"I5","note":"8"},{"key":"I13","note":"7"},{"key":"I6","note":"13"},{"key":"I8","note":"20"},{"key":"I16","note":"17"},{"key":"I21","note":"8"},{"key":"I31","note":"7"}]},{"v":"I21","state":"waiting"}]},{"say":"Pass 2. I31 to I40: 7 + 3 = 10, shorter than 11, so I40's distance becomes 10.","ops":[{"v":"I40","state":"current"},{"e":["I31","I40"],"state":"tree"},{"panel":"dist","set":{"I40":"10"}},{"panel":"changed","list":[{"key":"I5","note":"8"},{"key":"I13","note":"7"},{"key":"I6","note":"13"},{"key":"I8","note":"20"},{"key":"I16","note":"17"},{"key":"I21","note":"8"},{"key":"I31","note":"7"},{"key":"I40","note":"10"}]},{"e":["I41","I40"],"state":"idle"},{"v":"I31","state":"waiting"}]},{"say":"Pass 2. I40 to I39: 10 + 2 = 12, so I39's distance becomes 12.","ops":[{"v":"I39","state":"current"},{"e":["I40","I39"],"state":"tree"},{"panel":"dist","set":{"I39":"12"}},{"panel":"changed","list":[{"key":"I5","note":"8"},{"key":"I13","note":"7"},{"key":"I6","note":"13"},{"key":"I8","note":"20"},{"key":"I16","note":"17"},{"key":"I21","note":"8"},{"key":"I31","note":"7"},{"key":"I40","note":"10"},{"key":"I39","note":"12"}]},{"v":"I40","state":"waiting"}]},{"say":"Pass 2 done. 9 distances changed.","ops":[{"v":"I5","state":"done"},{"v":"I13","state":"done"},{"v":"I6","state":"done"},{"v":"I8","state":"done"},{"v":"I16","state":"done"},{"v":"I21","state":"done"},{"v":"I31","state":"done"},{"v":"I40","state":"done"},{"v":"I39","state":"done"}]},{"say":"Pass 3. I6 to I7: 13 + 4 = 17, so I7's distance becomes 17.","ops":[{"v":"I7","state":"current"},{"e":["I6","I7"],"state":"tree"},{"panel":"dist","set":{"I7":"17"}},{"panel":"changed","list":[{"key":"I7","note":"17"}]}]},{"say":"Pass 3. I8 to I9: 20 + 4 = 24, so I9's distance becomes 24.","ops":[{"v":"I9","state":"current"},{"e":["I8","I9"],"state":"tree"},{"panel":"dist","set":{"I9":"24"}},{"panel":"changed","list":[{"key":"I7","note":"17"},{"key":"I9","note":"24"}]},{"v":"I7","state":"waiting"}]},{"say":"Pass 3. I9 to I18: 24 + 2 = 26, so I18's distance becomes 26.","ops":[{"v":"I18","state":"current"},{"e":["I9","I18"],"state":"tree"},{"panel":"dist","set":{"I18":"26"}},{"panel":"changed","list":[{"key":"I7","note":"17"},{"key":"I9","note":"24"},{"key":"I18","note":"26"}]},{"v":"I9","state":"waiting"}]},{"say":"Pass 3. I13 to I12: 7 + 5 = 12, so I12's distance becomes 12.","ops":[{"v":"I12","state":"current"},{"e":["I13","I12"],"state":"tree"},{"panel":"dist","set":{"I12":"12"}},{"panel":"changed","list":[{"key":"I7","note":"17"},{"key":"I9","note":"24"},{"key":"I18","note":"26"},{"key":"I12","note":"12"}]},{"v":"I18","state":"waiting"}]},{"say":"Pass 3. I21 to I12: 8 + 2 = 10, shorter than 12, so I12's distance becomes 10.","ops":[{"v":"I12","state":"current"},{"e":["I21","I12"],"state":"tree"},{"panel":"dist","set":{"I12":"10"}},{"panel":"changed","list":[{"key":"I7","note":"17"},{"key":"I9","note":"24"},{"key":"I18","note":"26"},{"key":"I12","note":"10"}]},{"e":["I13","I12"],"state":"idle"}]},{"say":"Pass 3. I21 to I20: 8 + 2 = 10, so I20's distance becomes 10.","ops":[{"v":"I20","state":"current"},{"e":["I21","I20"],"state":"tree"},{"panel":"dist","set":{"I20":"10"}},{"panel":"changed","list":[{"key":"I7","note":"17"},{"key":"I9","note":"24"},{"key":"I18","note":"26"},{"key":"I12","note":"10"},{"key":"I20","note":"10"}]},{"v":"I12","state":"waiting"}]},{"say":"Pass 3. I39 to I30: 12 + 3 = 15, so I30's distance becomes 15.","ops":[{"v":"I30","state":"current"},{"e":["I39","I30"],"state":"tree"},{"panel":"dist","set":{"I30":"15"}},{"panel":"changed","list":[{"key":"I7","note":"17"},{"key":"I9","note":"24"},{"key":"I18","note":"26"},{"key":"I12","note":"10"},{"key":"I20","note":"10"},{"key":"I30","note":"15"}]},{"v":"I20","state":"waiting"}]},{"say":"Pass 3. I39 to I38: 12 + 2 = 14, so I38's distance becomes 14.","ops":[{"v":"I38","state":"current"},{"e":["I39","I38"],"state":"tree"},{"panel":"dist","set":{"I38":"14"}},{"panel":"changed","list":[{"key":"I7","note":"17"},{"key":"I9","note":"24"},{"key":"I18","note":"26"},{"key":"I12","note":"10"},{"key":"I20","note":"10"},{"key":"I30","note":"15"},{"key":"I38","note":"14"}]},{"v":"I30","state":"waiting"}]},{"say":"Pass 3 done. 7 distances changed.","ops":[{"v":"I7","state":"done"},{"v":"I9","state":"done"},{"v":"I18","state":"done"},{"v":"I12","state":"done"},{"v":"I20","state":"done"},{"v":"I30","state":"done"},{"v":"I38","state":"done"}]},{"say":"Pass 4. I12 to I3: 10 + 4 = 14, so I3's distance becomes 14.","ops":[{"v":"I3","state":"current"},{"e":["I12","I3"],"state":"tree"},{"panel":"dist","set":{"I3":"14"}},{"panel":"changed","list":[{"key":"I3","note":"14"}]}]},{"say":"Pass 4. I12 to I11: 10 + 5 = 15, so I11's distance becomes 15.","ops":[{"v":"I11","state":"current"},{"e":["I12","I11"],"state":"tree"},{"panel":"dist","set":{"I11":"15"}},{"panel":"changed","list":[{"key":"I3","note":"14"},{"key":"I11","note":"15"}]},{"v":"I3","state":"waiting"}]},{"say":"Pass 4. I20 to I19: 10 + 3 = 13, so I19's distance becomes 13.","ops":[{"v":"I19","state":"current"},{"e":["I20","I19"],"state":"tree"},{"panel":"dist","set":{"I19":"13"}},{"panel":"changed","list":[{"key":"I3","note":"14"},{"key":"I11","note":"15"},{"key":"I19","note":"13"}]},{"v":"I11","state":"waiting"}]},{"say":"Pass 4. I20 to I29: 10 + 3 = 13, so I29's distance becomes 13.","ops":[{"v":"I29","state":"current"},{"e":["I20","I29"],"state":"tree"},{"panel":"dist","set":{"I29":"13"}},{"panel":"changed","list":[{"key":"I3","note":"14"},{"key":"I11","note":"15"},{"key":"I19","note":"13"},{"key":"I29","note":"13"}]},{"v":"I19","state":"waiting"}]},{"say":"Pass 4. I38 to I37: 14 + 3 = 17, so I37's distance becomes 17.","ops":[{"v":"I37","state":"current"},{"e":["I38","I37"],"state":"tree"},{"panel":"dist","set":{"I37":"17"}},{"panel":"changed","list":[{"key":"I3","note":"14"},{"key":"I11","note":"15"},{"key":"I19","note":"13"},{"key":"I29","note":"13"},{"key":"I37","note":"17"}]},{"v":"I29","state":"waiting"}]},{"say":"Pass 4 done. 5 distances changed.","ops":[{"v":"I3","state":"done"},{"v":"I11","state":"done"},{"v":"I19","state":"done"},{"v":"I29","state":"done"},{"v":"I37","state":"done"}]},{"say":"Pass 5. I3 to I4: 14 + 3 = 17, so I4's distance becomes 17.","ops":[{"v":"I4","state":"current"},{"e":["I3","I4"],"state":"tree"},{"panel":"dist","set":{"I4":"17"}},{"panel":"changed","list":[{"key":"I4","note":"17"}]}]},{"say":"Pass 5. I11 to I10: 15 + 4 = 19, so I10's distance becomes 19.","ops":[{"v":"I10","state":"current"},{"e":["I11","I10"],"state":"tree"},{"panel":"dist","set":{"I10":"19"}},{"panel":"changed","list":[{"key":"I4","note":"17"},{"key":"I10","note":"19"}]},{"v":"I4","state":"waiting"}]},{"say":"Pass 5. I19 to I10: 13 + 5 = 18, shorter than 19, so I10's distance becomes 18.","ops":[{"v":"I10","state":"current"},{"e":["I19","I10"],"state":"tree"},{"panel":"dist","set":{"I10":"18"}},{"panel":"changed","list":[{"key":"I4","note":"17"},{"key":"I10","note":"18"}]},{"e":["I11","I10"],"state":"idle"}]},{"say":"Pass 5. I37 to I28: 17 + 4 = 21, so I28's distance becomes 21.","ops":[{"v":"I28","state":"current"},{"e":["I37","I28"],"state":"tree"},{"panel":"dist","set":{"I28":"21"}},{"panel":"changed","list":[{"key":"I4","note":"17"},{"key":"I10","note":"18"},{"key":"I28","note":"21"}]},{"v":"I10","state":"waiting"}]},{"say":"Pass 5 done. The distances of I4, I10 and I28 changed.","ops":[{"v":"I4","state":"done"},{"v":"I10","state":"done"},{"v":"I28","state":"done"}]},{"say":"Pass 6. I10 to I1: 18 + 5 = 23, so I1's distance becomes 23.","ops":[{"v":"I1","state":"current"},{"e":["I10","I1"],"state":"tree"},{"panel":"dist","set":{"I1":"23"}},{"panel":"changed","list":[{"key":"I1","note":"23"}]}]},{"say":"Pass 6 done. I1's distance changed.","ops":[{"v":"I1","state":"done"}]},{"say":"Pass 7. I1 to I2: 23 + 3 = 26, so I2's distance becomes 26.","ops":[{"v":"I2","state":"current"},{"e":["I1","I2"],"state":"tree"},{"panel":"dist","set":{"I2":"26"}},{"panel":"changed","list":[{"key":"I2","note":"26"}]}]},{"say":"Pass 7 done. I2's distance changed.","ops":[{"v":"I2","state":"done"}]},{"say":"Pass 8 done. No distance changed, so later passes won't change any either, but gograph runs them all.","ops":[{"panel":"changed","list":[]}]},{"say":"Pass 9 done. No distance changed."},{"say":"Pass 10 done. No distance changed."},{"say":"Pass 11 done. No distance changed."},{"say":"Pass 12 done. No distance changed."},{"say":"Pass 13 done. No distance changed."},{"say":"Pass 14 done. No distance changed."},{"say":"Pass 15 done. No distance changed."},{"say":"Pass 16 done. No distance changed."},{"say":"Pass 17 done. No distance changed."},{"say":"Pass 18 done. No distance changed."},{"say":"Pass 19 done. No distance changed."},{"say":"Pass 20 done. No distance changed."},{"say":"Pass 21 done. No distance changed."},{"say":"Pass 22 done. No distance changed."},{"say":"Pass 23 done. No distance changed."},{"say":"Pass 24 done. No distance changed."},{"say":"Pass 25 done. No distance changed."},{"say":"Pass 26 done. No distance changed."},{"say":"Pass 27 done. No distance changed."},{"say":"Pass 28 done. No distance changed."},{"say":"Pass 29 done. No distance changed."},{"say":"Pass 30 done. No distance changed."},{"say":"Pass 31 done. No distance changed."},{"say":"Pass 32 done. No distance changed."},{"say":"Pass 33 done. No distance changed."},{"say":"Pass 34 done. No distance changed."},{"say":"Pass 35 done. No distance changed."},{"say":"Pass 36 done. No distance changed."},{"say":"Pass 37 done. No distance changed."},{"say":"Pass 38 done. No distance changed."},{"say":"Pass 39 done. No distance changed."},{"say":"Pass 40 done. No distance changed."},{"say":"Pass 41 done. No distance changed."},{"say":"Pass 42 done. No distance changed."},{"say":"Pass 43 done. No distance changed."},{"say":"Pass 44 done. No distance changed."},{"say":"Extra pass. No edge gives a shorter distance, so there is no negative cycle. Every distance from I23 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, \"I23\")\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(\"I2\")\nif !ok {\n\treturn nil // out of reach\n}\nroute, _ := paths.PathTo(\"I2\")\nfmt.Println(dist)\nfor _, v := range route {\n\tfmt.Println(v.Label())\n}"}
