{"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":"fx-majors","name":"Major currencies","description":"Six major currencies and the rates a dealer quotes between them. Each edge is a trade, and its weight is minus the natural log of the exchange rate, so the shortest path is the best rate. Dollars buy more francs through EUR than directly. The rates are illustrative and close to market rates, and every loop of trades loses a little to the spread.","family":"currency","directed":true,"weighted":true,"acyclic":false,"vertices":[{"id":"CAD","x":736,"y":592},{"id":"CHF","x":152,"y":256},{"id":"EUR","x":500,"y":96},{"id":"GBP","x":848,"y":256},{"id":"JPY","x":264,"y":592},{"id":"USD","x":500,"y":352}],"edges":[{"from":"CAD","to":"USD","weight":0.319819664},{"from":"CAD","to":"GBP","weight":0.579175845},{"from":"CAD","to":"JPY","weight":-4.691806493},{"from":"CHF","to":"USD","weight":-0.156490797},{"from":"CHF","to":"JPY","weight":-5.170143028},{"from":"CHF","to":"EUR","weight":-0.065225785},{"from":"EUR","to":"USD","weight":-0.094309679},{"from":"EUR","to":"GBP","weight":0.168560674},{"from":"EUR","to":"CHF","weight":0.069210752},{"from":"GBP","to":"USD","weight":-0.260901657},{"from":"GBP","to":"EUR","weight":-0.165514438},{"from":"GBP","to":"CAD","weight":-0.575151622},{"from":"JPY","to":"USD","weight":5.011635794},{"from":"JPY","to":"CAD","weight":4.699832576},{"from":"JPY","to":"CHF","weight":5.176152833},{"from":"USD","to":"EUR","weight":0.096312682},{"from":"USD","to":"GBP","weight":0.263861385},{"from":"USD","to":"JPY","weight":-5.009634794},{"from":"USD","to":"CHF","weight":0.168537002},{"from":"USD","to":"CAD","weight":-0.309834877}],"details":{"vertices":6,"edges":20,"directed":true,"weighted":true,"acyclic":false,"weightMin":-5.170143028,"weightMax":5.176152833,"negativeWeights":true,"density":0.6666666666666666,"inDegree":{"min":3,"avg":3.3333333333333335,"max":5},"outDegree":{"min":3,"avg":3.3333333333333335,"max":5},"selfLoops":0,"components":1}},"problem":"What is the best rate between every pair of currencies, trading through other currencies when that pays more?","params":{},"result":{"kind":"all-pairs","values":{"CAD":{"CAD":0,"CHF":0.48287215899999997,"EUR":0.413661407,"GBP":0.579175845,"JPY":-4.691806493,"USD":0.31827418799999996},"CHF":{"CAD":-0.47181673300000004,"CHF":0,"EUR":-0.065225785,"GBP":0.103334889,"JPY":-5.170143028,"USD":-0.159535464},"EUR":{"CAD":-0.40659094800000006,"CHF":0.069210752,"EUR":0,"GBP":0.168560674,"JPY":-5.103944473,"USD":-0.094309679},"GBP":{"CAD":-0.575151622,"CHF":-0.09630368600000001,"EUR":-0.165514438,"GBP":0,"JPY":-5.270536451,"USD":-0.260901657},"JPY":{"CAD":4.699832576,"CHF":5.176152833,"EUR":5.107948476,"GBP":5.275497179,"JPY":0,"USD":5.011635794},"USD":{"CAD":-0.311290237,"CHF":0.165523434,"EUR":0.096312682,"GBP":0.263861385,"JPY":-5.009634794,"USD":0}}},"answer":"All 30 pairs of different vertices have a path. At the best rates, 1 CAD buys 109.05 JPY, 0.7274 USD, 0.66122 EUR, 0.61701 CHF and 0.56036 GBP.","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 6 rounds, one per vertex, and each round lets paths stop at one more vertex.","ops":[{"panel":"dist","cells":[{"row":"CAD","col":"CAD","value":"0"},{"row":"CAD","col":"CHF","value":"∞"},{"row":"CAD","col":"EUR","value":"∞"},{"row":"CAD","col":"GBP","value":"0.5792"},{"row":"CAD","col":"JPY","value":"-4.6918"},{"row":"CAD","col":"USD","value":"0.3198"},{"row":"CHF","col":"CAD","value":"∞"},{"row":"CHF","col":"CHF","value":"0"},{"row":"CHF","col":"EUR","value":"-0.0652"},{"row":"CHF","col":"GBP","value":"∞"},{"row":"CHF","col":"JPY","value":"-5.1701"},{"row":"CHF","col":"USD","value":"-0.1565"},{"row":"EUR","col":"CAD","value":"∞"},{"row":"EUR","col":"CHF","value":"0.0692"},{"row":"EUR","col":"EUR","value":"0"},{"row":"EUR","col":"GBP","value":"0.1686"},{"row":"EUR","col":"JPY","value":"∞"},{"row":"EUR","col":"USD","value":"-0.0943"},{"row":"GBP","col":"CAD","value":"-0.5752"},{"row":"GBP","col":"CHF","value":"∞"},{"row":"GBP","col":"EUR","value":"-0.1655"},{"row":"GBP","col":"GBP","value":"0"},{"row":"GBP","col":"JPY","value":"∞"},{"row":"GBP","col":"USD","value":"-0.2609"},{"row":"JPY","col":"CAD","value":"4.6998"},{"row":"JPY","col":"CHF","value":"5.1762"},{"row":"JPY","col":"EUR","value":"∞"},{"row":"JPY","col":"GBP","value":"∞"},{"row":"JPY","col":"JPY","value":"0"},{"row":"JPY","col":"USD","value":"5.0116"},{"row":"USD","col":"CAD","value":"-0.3098"},{"row":"USD","col":"CHF","value":"0.1685"},{"row":"USD","col":"EUR","value":"0.0963"},{"row":"USD","col":"GBP","value":"0.2639"},{"row":"USD","col":"JPY","value":"-5.0096"},{"row":"USD","col":"USD","value":"0"}]}]},{"say":"Round 1 of 6: paths may now go through CAD. 2 pairs that had no path get one.","ops":[{"v":"CAD","state":"current"}]},{"say":"GBP to JPY through CAD: -0.5752 - 4.6918 = -5.267, so the distance becomes -5.267: 1 GBP buys 193.83 JPY this way.","ops":[{"panel":"dist","cells":[{"row":"GBP","col":"JPY","value":"-5.267"}]},{"v":"GBP","state":"waiting"},{"v":"JPY","state":"waiting"}]},{"say":"JPY to GBP through CAD: 4.6998 + 0.5792 = 5.279, so the distance becomes 5.279: 1 JPY buys 0.0050975 GBP this way.","ops":[{"panel":"dist","cells":[{"row":"JPY","col":"GBP","value":"5.279"}]}]},{"say":"Round 2 of 6: paths may now go through CHF. 2 pairs that had no path get one.","ops":[{"v":"CHF","state":"current"},{"v":"CAD","state":"done"},{"v":"JPY","state":"idle"},{"v":"GBP","state":"idle"}]},{"say":"EUR to JPY through CHF: 0.0692 - 5.1701 = -5.1009, so the distance becomes -5.1009: 1 EUR buys 164.17 JPY this way.","ops":[{"panel":"dist","cells":[{"row":"EUR","col":"JPY","value":"-5.1009"}]},{"v":"EUR","state":"waiting"},{"v":"JPY","state":"waiting"}]},{"say":"JPY to EUR through CHF: 5.1762 - 0.0652 = 5.1109, so the distance becomes 5.1109: 1 JPY buys 0.0060305 EUR this way.","ops":[{"panel":"dist","cells":[{"row":"JPY","col":"EUR","value":"5.1109"}]}]},{"say":"Round 3 of 6: paths may now go through EUR. 4 distances get shorter, 2 of them for pairs that had no path before.","ops":[{"v":"EUR","state":"current"},{"v":"CHF","state":"done"},{"v":"JPY","state":"idle"}]},{"say":"CHF to GBP through EUR: -0.0652 + 0.1686 = 0.1033, so the distance becomes 0.1033: 1 CHF buys 0.90182 GBP this way.","ops":[{"panel":"dist","cells":[{"row":"CHF","col":"GBP","value":"0.1033"}]},{"v":"CHF","state":"waiting"},{"v":"GBP","state":"waiting"}]},{"say":"CHF to USD through EUR: -0.0652 - 0.0943 = -0.1595, shorter than -0.1565, so the distance becomes -0.1595: 1 CHF buys 1.173 USD this way.","ops":[{"panel":"dist","cells":[{"row":"CHF","col":"USD","value":"-0.1595"}]},{"v":"GBP","state":"idle"},{"v":"USD","state":"waiting"}]},{"say":"GBP to CHF through EUR: -0.1655 + 0.0692 = -0.0963, so the distance becomes -0.0963: 1 GBP buys 1.1011 CHF this way.","ops":[{"panel":"dist","cells":[{"row":"GBP","col":"CHF","value":"-0.0963"}]},{"v":"USD","state":"idle"},{"v":"GBP","state":"waiting"}]},{"say":"USD to CHF through EUR: 0.0963 + 0.0692 = 0.1655, shorter than 0.1685, so the distance becomes 0.1655: 1 USD buys 0.84745 CHF this way.","ops":[{"panel":"dist","cells":[{"row":"USD","col":"CHF","value":"0.1655"}]},{"v":"GBP","state":"idle"},{"v":"USD","state":"waiting"}]},{"say":"Round 4 of 6: paths may now go through GBP. 6 distances get shorter, 4 of them for pairs that had no path before.","ops":[{"v":"GBP","state":"current"},{"v":"EUR","state":"done"},{"v":"USD","state":"idle"},{"v":"CHF","state":"done"}]},{"say":"CAD to CHF through GBP: 0.5792 - 0.0963 = 0.4829, so the distance becomes 0.4829: 1 CAD buys 0.61701 CHF this way.","ops":[{"panel":"dist","cells":[{"row":"CAD","col":"CHF","value":"0.4829"}]},{"v":"CAD","state":"waiting"},{"v":"CHF","state":"waiting"}]},{"say":"CAD to EUR through GBP: 0.5792 - 0.1655 = 0.4137, so the distance becomes 0.4137: 1 CAD buys 0.66122 EUR this way.","ops":[{"panel":"dist","cells":[{"row":"CAD","col":"EUR","value":"0.4137"}]},{"v":"CHF","state":"done"},{"v":"EUR","state":"waiting"}]},{"say":"CAD to USD through GBP: 0.5792 - 0.2609 = 0.3183, shorter than 0.3198, so the distance becomes 0.3183: 1 CAD buys 0.7274 USD this way.","ops":[{"panel":"dist","cells":[{"row":"CAD","col":"USD","value":"0.3183"}]},{"v":"EUR","state":"done"},{"v":"USD","state":"waiting"}]},{"say":"CHF to CAD through GBP: 0.1033 - 0.5752 = -0.4718, so the distance becomes -0.4718: 1 CHF buys 1.6029 CAD this way.","ops":[{"panel":"dist","cells":[{"row":"CHF","col":"CAD","value":"-0.4718"}]},{"v":"USD","state":"idle"},{"v":"CHF","state":"waiting"}]},{"say":"EUR to CAD through GBP: 0.1686 - 0.5752 = -0.4066, so the distance becomes -0.4066: 1 EUR buys 1.5017 CAD this way.","ops":[{"panel":"dist","cells":[{"row":"EUR","col":"CAD","value":"-0.4066"}]},{"v":"CHF","state":"done"},{"v":"EUR","state":"waiting"}]},{"say":"USD to CAD through GBP: 0.2639 - 0.5752 = -0.3113, shorter than -0.3098, so the distance becomes -0.3113: 1 USD buys 1.3652 CAD this way.","ops":[{"panel":"dist","cells":[{"row":"USD","col":"CAD","value":"-0.3113"}]},{"v":"EUR","state":"done"},{"v":"USD","state":"waiting"}]},{"say":"Round 5 of 6: paths may now go through JPY. No distance gets shorter.","ops":[{"v":"JPY","state":"current"},{"v":"GBP","state":"done"},{"v":"USD","state":"idle"},{"v":"CAD","state":"done"}]},{"say":"Round 6 of 6: paths may now go through USD. 4 distances get shorter.","ops":[{"v":"USD","state":"current"},{"v":"JPY","state":"done"}]},{"say":"EUR to JPY through USD: -0.0943 - 5.0096 = -5.1039, shorter than -5.1009, so the distance becomes -5.1039: 1 EUR buys 164.67 JPY this way.","ops":[{"panel":"dist","cells":[{"row":"EUR","col":"JPY","value":"-5.1039"}]},{"v":"EUR","state":"waiting"},{"v":"JPY","state":"waiting"}]},{"say":"GBP to JPY through USD: -0.2609 - 5.0096 = -5.2705, shorter than -5.267, so the distance becomes -5.2705: 1 GBP buys 194.52 JPY this way.","ops":[{"panel":"dist","cells":[{"row":"GBP","col":"JPY","value":"-5.2705"}]},{"v":"EUR","state":"done"},{"v":"GBP","state":"waiting"}]},{"say":"JPY to EUR through USD: 5.0116 + 0.0963 = 5.1079, shorter than 5.1109, so the distance becomes 5.1079: 1 JPY buys 0.0060485 EUR this way.","ops":[{"panel":"dist","cells":[{"row":"JPY","col":"EUR","value":"5.1079"}]},{"v":"GBP","state":"done"},{"v":"EUR","state":"waiting"}]},{"say":"JPY to GBP through USD: 5.0116 + 0.2639 = 5.2755, shorter than 5.279, so the distance becomes 5.2755: 1 JPY buys 0.0051154 GBP this way.","ops":[{"panel":"dist","cells":[{"row":"JPY","col":"GBP","value":"5.2755"}]},{"v":"EUR","state":"done"},{"v":"GBP","state":"waiting"}]},{"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.","ops":[{"v":"USD","state":"done"},{"v":"JPY","state":"done"},{"v":"GBP","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[\"CAD\"][\"GBP\"])\nfmt.Println(dist[\"GBP\"][\"CAD\"]) // +Inf when there is no path"}
