{"algorithm":"floyd-warshall","about":["Floyd-Warshall fills a table with a distance for every pair of vertices: the edge's weight where there is an edge, 0 from a vertex to itself, and infinity everywhere else. Then it takes each vertex in turn as a stop on the way. For every pair, if going through that stop is shorter than the distance in the table, the table takes the shorter one. After the last vertex, each entry is the shortest distance by any route.","It allows negative weights. A vertex that ends with a negative distance to itself is on a negative cycle, and path.FloydWarshall returns ErrNegativeWeightCycle. It needs a directed, weighted graph.","Three loops over the vertices make it O(V³) in time and O(V²) in memory, whatever the number of edges. It suits small or dense graphs where you want every distance at once, such as a table of travel times between all the stops of a route. On a large graph with few edges, running Dijkstra from each vertex costs less."],"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 between every pair of stops, so a route can start anywhere, not just at the depot?","params":{},"result":{"kind":"all-pairs","values":{"Bakery":{"Bakery":0,"Clinic":null,"Depot":null,"Library":8,"Market":null,"Park":7,"School":5,"Station":13},"Clinic":{"Bakery":null,"Clinic":0,"Depot":null,"Library":null,"Market":null,"Park":null,"School":null,"Station":2},"Depot":{"Bakery":3,"Clinic":12,"Depot":0,"Library":11,"Market":2,"Park":10,"School":8,"Station":14},"Library":{"Bakery":null,"Clinic":null,"Depot":null,"Library":0,"Market":null,"Park":null,"School":null,"Station":5},"Market":{"Bakery":1,"Clinic":10,"Depot":null,"Library":9,"Market":0,"Park":8,"School":6,"Station":12},"Park":{"Bakery":null,"Clinic":null,"Depot":null,"Library":2,"Market":null,"Park":0,"School":null,"Station":6},"School":{"Bakery":null,"Clinic":null,"Depot":null,"Library":3,"Market":null,"Park":null,"School":0,"Station":8},"Station":{"Bakery":null,"Clinic":null,"Depot":null,"Library":null,"Market":null,"Park":null,"School":null,"Station":0}}},"answer":"23 of the 56 pairs of different vertices have a path. The longest of the shortest distances is 14, from Depot to Station.","legend":{"vertex":[{"id":"idle","label":"Not a stop yet","color":"#64748B","shape":"hollow"},{"id":"waiting","label":"Pair that got shorter","color":"#E69F00","shape":"dashed-square"},{"id":"current","label":"Stop added this round","color":"#56B4E9","shape":"ring"},{"id":"done","label":"Allowed as a stop","color":"#009E73","shape":"filled"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"}],"panels":[{"id":"dist","title":"Distances","kind":"matrix"}]},"steps":[{"say":"Each distance starts as the weight of the edge from one vertex to the other, ∞ where there is no edge, and 0 from a vertex to itself. Floyd-Warshall then runs 8 rounds, one per vertex, and each round lets paths stop at one more vertex.","ops":[{"panel":"dist","cells":[{"row":"Depot","col":"Depot","value":"0"},{"row":"Depot","col":"Bakery","value":"4"},{"row":"Depot","col":"Market","value":"2"},{"row":"Depot","col":"School","value":"∞"},{"row":"Depot","col":"Park","value":"∞"},{"row":"Depot","col":"Clinic","value":"∞"},{"row":"Depot","col":"Library","value":"∞"},{"row":"Depot","col":"Station","value":"∞"},{"row":"Bakery","col":"Depot","value":"∞"},{"row":"Bakery","col":"Bakery","value":"0"},{"row":"Bakery","col":"Market","value":"∞"},{"row":"Bakery","col":"School","value":"5"},{"row":"Bakery","col":"Park","value":"7"},{"row":"Bakery","col":"Clinic","value":"∞"},{"row":"Bakery","col":"Library","value":"∞"},{"row":"Bakery","col":"Station","value":"∞"},{"row":"Market","col":"Depot","value":"∞"},{"row":"Market","col":"Bakery","value":"1"},{"row":"Market","col":"Market","value":"0"},{"row":"Market","col":"School","value":"∞"},{"row":"Market","col":"Park","value":"8"},{"row":"Market","col":"Clinic","value":"10"},{"row":"Market","col":"Library","value":"∞"},{"row":"Market","col":"Station","value":"∞"},{"row":"School","col":"Depot","value":"∞"},{"row":"School","col":"Bakery","value":"∞"},{"row":"School","col":"Market","value":"∞"},{"row":"School","col":"School","value":"0"},{"row":"School","col":"Park","value":"∞"},{"row":"School","col":"Clinic","value":"∞"},{"row":"School","col":"Library","value":"3"},{"row":"School","col":"Station","value":"∞"},{"row":"Park","col":"Depot","value":"∞"},{"row":"Park","col":"Bakery","value":"∞"},{"row":"Park","col":"Market","value":"∞"},{"row":"Park","col":"School","value":"∞"},{"row":"Park","col":"Park","value":"0"},{"row":"Park","col":"Clinic","value":"∞"},{"row":"Park","col":"Library","value":"2"},{"row":"Park","col":"Station","value":"6"},{"row":"Clinic","col":"Depot","value":"∞"},{"row":"Clinic","col":"Bakery","value":"∞"},{"row":"Clinic","col":"Market","value":"∞"},{"row":"Clinic","col":"School","value":"∞"},{"row":"Clinic","col":"Park","value":"∞"},{"row":"Clinic","col":"Clinic","value":"0"},{"row":"Clinic","col":"Library","value":"∞"},{"row":"Clinic","col":"Station","value":"2"},{"row":"Library","col":"Depot","value":"∞"},{"row":"Library","col":"Bakery","value":"∞"},{"row":"Library","col":"Market","value":"∞"},{"row":"Library","col":"School","value":"∞"},{"row":"Library","col":"Park","value":"∞"},{"row":"Library","col":"Clinic","value":"∞"},{"row":"Library","col":"Library","value":"0"},{"row":"Library","col":"Station","value":"5"},{"row":"Station","col":"Depot","value":"∞"},{"row":"Station","col":"Bakery","value":"∞"},{"row":"Station","col":"Market","value":"∞"},{"row":"Station","col":"School","value":"∞"},{"row":"Station","col":"Park","value":"∞"},{"row":"Station","col":"Clinic","value":"∞"},{"row":"Station","col":"Library","value":"∞"},{"row":"Station","col":"Station","value":"0"}]}]},{"say":"Round 1 of 8: paths may now go through Depot. No distance gets shorter.","ops":[{"v":"Depot","state":"current"}]},{"say":"Round 2 of 8: paths may now go through Bakery. 3 pairs that had no path get one.","ops":[{"v":"Bakery","state":"current"},{"v":"Depot","state":"done"}]},{"say":"Depot to School through Bakery: 4 + 5 = 9, so the distance becomes 9.","ops":[{"panel":"dist","cells":[{"row":"Depot","col":"School","value":"9"}]},{"v":"Depot","state":"waiting"},{"v":"School","state":"waiting"}]},{"say":"Depot to Park through Bakery: 4 + 7 = 11, so the distance becomes 11.","ops":[{"panel":"dist","cells":[{"row":"Depot","col":"Park","value":"11"}]},{"v":"School","state":"idle"},{"v":"Park","state":"waiting"}]},{"say":"Market to School through Bakery: 1 + 5 = 6, so the distance becomes 6.","ops":[{"panel":"dist","cells":[{"row":"Market","col":"School","value":"6"}]},{"v":"Depot","state":"done"},{"v":"Park","state":"idle"},{"v":"Market","state":"waiting"},{"v":"School","state":"waiting"}]},{"say":"Round 3 of 8: paths may now go through Market. 4 distances get shorter, 1 of them for a pair that had no path before.","ops":[{"v":"Market","state":"current"},{"v":"Bakery","state":"done"},{"v":"School","state":"idle"}]},{"say":"Depot to Bakery through Market: 2 + 1 = 3, shorter than 4, so the distance becomes 3.","ops":[{"panel":"dist","cells":[{"row":"Depot","col":"Bakery","value":"3"}]},{"v":"Depot","state":"waiting"},{"v":"Bakery","state":"waiting"}]},{"say":"Depot to School through Market: 2 + 6 = 8, shorter than 9, so the distance becomes 8.","ops":[{"panel":"dist","cells":[{"row":"Depot","col":"School","value":"8"}]},{"v":"Bakery","state":"done"},{"v":"School","state":"waiting"}]},{"say":"Depot to Park through Market: 2 + 8 = 10, shorter than 11, so the distance becomes 10.","ops":[{"panel":"dist","cells":[{"row":"Depot","col":"Park","value":"10"}]},{"v":"School","state":"idle"},{"v":"Park","state":"waiting"}]},{"say":"Depot to Clinic through Market: 2 + 10 = 12, so the distance becomes 12.","ops":[{"panel":"dist","cells":[{"row":"Depot","col":"Clinic","value":"12"}]},{"v":"Park","state":"idle"},{"v":"Clinic","state":"waiting"}]},{"say":"Round 4 of 8: paths may now go through School. 3 pairs that had no path get one.","ops":[{"v":"School","state":"current"},{"v":"Market","state":"done"},{"v":"Depot","state":"done"},{"v":"Clinic","state":"idle"}]},{"say":"Depot to Library through School: 8 + 3 = 11, so the distance becomes 11.","ops":[{"panel":"dist","cells":[{"row":"Depot","col":"Library","value":"11"}]},{"v":"Depot","state":"waiting"},{"v":"Library","state":"waiting"}]},{"say":"Bakery to Library through School: 5 + 3 = 8, so the distance becomes 8.","ops":[{"panel":"dist","cells":[{"row":"Bakery","col":"Library","value":"8"}]},{"v":"Depot","state":"done"},{"v":"Bakery","state":"waiting"}]},{"say":"Market to Library through School: 6 + 3 = 9, so the distance becomes 9.","ops":[{"panel":"dist","cells":[{"row":"Market","col":"Library","value":"9"}]},{"v":"Bakery","state":"done"},{"v":"Market","state":"waiting"}]},{"say":"Round 5 of 8: paths may now go through Park. 3 pairs that had no path get one.","ops":[{"v":"Park","state":"current"},{"v":"School","state":"done"},{"v":"Market","state":"done"},{"v":"Library","state":"idle"}]},{"say":"Depot to Station through Park: 10 + 6 = 16, so the distance becomes 16.","ops":[{"panel":"dist","cells":[{"row":"Depot","col":"Station","value":"16"}]},{"v":"Depot","state":"waiting"},{"v":"Station","state":"waiting"}]},{"say":"Bakery to Station through Park: 7 + 6 = 13, so the distance becomes 13.","ops":[{"panel":"dist","cells":[{"row":"Bakery","col":"Station","value":"13"}]},{"v":"Depot","state":"done"},{"v":"Bakery","state":"waiting"}]},{"say":"Market to Station through Park: 8 + 6 = 14, so the distance becomes 14.","ops":[{"panel":"dist","cells":[{"row":"Market","col":"Station","value":"14"}]},{"v":"Bakery","state":"done"},{"v":"Market","state":"waiting"}]},{"say":"Round 6 of 8: paths may now go through Clinic. 2 distances get shorter.","ops":[{"v":"Clinic","state":"current"},{"v":"Park","state":"done"},{"v":"Market","state":"done"},{"v":"Station","state":"idle"}]},{"say":"Depot to Station through Clinic: 12 + 2 = 14, shorter than 16, so the distance becomes 14.","ops":[{"panel":"dist","cells":[{"row":"Depot","col":"Station","value":"14"}]},{"v":"Depot","state":"waiting"},{"v":"Station","state":"waiting"}]},{"say":"Market to Station through Clinic: 10 + 2 = 12, shorter than 14, so the distance becomes 12.","ops":[{"panel":"dist","cells":[{"row":"Market","col":"Station","value":"12"}]},{"v":"Depot","state":"done"},{"v":"Market","state":"waiting"}]},{"say":"Round 7 of 8: paths may now go through Library. 1 pair that had no path gets one.","ops":[{"v":"Library","state":"current"},{"v":"Clinic","state":"done"},{"v":"Market","state":"done"},{"v":"Station","state":"idle"}]},{"say":"School to Station through Library: 3 + 5 = 8, so the distance becomes 8.","ops":[{"panel":"dist","cells":[{"row":"School","col":"Station","value":"8"}]},{"v":"School","state":"waiting"},{"v":"Station","state":"waiting"}]},{"say":"Round 8 of 8: paths may now go through Station. No distance gets shorter.","ops":[{"v":"Station","state":"current"},{"v":"Library","state":"done"},{"v":"School","state":"done"}]},{"say":"Done. No vertex has a distance below 0 to itself, and no edge gives a shorter distance, so there is no negative cycle. Every distance is final. 33 pairs have no path, so their distances stay ∞.","ops":[{"v":"Station","state":"done"}]}],"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":"dist, err := path.FloydWarshall(g)\nif err != nil {\n\treturn err\n}\nfmt.Println(dist[\"Depot\"][\"Station\"])\nfmt.Println(dist[\"Station\"][\"Depot\"]) // +Inf when there is no path"}
