{"entities":{"Q7361196":{"pageid":31519127,"ns":120,"title":"Item:Q7361196","lastrevid":105363860,"modified":"2026-10-07T13:35:05Z","type":"item","id":"Q7361196","labels":{"en":{"language":"en","value":"The Floyd-Warshall Algorithm for Shortest Paths"}},"descriptions":{"en":{"language":"en","value":"AFP entry Floyd_Warshall"}},"aliases":{},"claims":{"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3dab7a8567366e0c45bc7b7bbc0b2d06282c4d50","datavalue":{"value":"https://isa-afp.org/entries/Floyd_Warshall.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q7361196$6FD1D928-4A61-440B-BF15-AD9719BBD0A2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3aaf1d9eb7be8ffa0ffc276984018b68fdacb27c","datavalue":{"value":{"time":"+2017-05-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q7361196$5FB54696-3234-4729-9E49-D3EEA536C6BE","rank":"normal"}],"P43":[{"mainsnak":{"snaktype":"value","property":"P43","hash":"8ad3851178fd4351b5225d703448b2fe1218d392","datavalue":{"value":"Simon Wimmer","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361196$9157D696-A607-4E45-AFC1-1D5ABC1E6799","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"7545c5768cca6bd4b47e52bfec18c22cb81849df","datavalue":{"value":"Peter Lammich","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361196$7D3B161F-E59E-4B07-BE7D-5EDB328AD430","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"266e23a0ce93c30b1fccdb338a9f8101a04ef161","datavalue":{"value":{"text":"The Floyd-Warshall Algorithm for Shortest Paths","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q7361196$684F15ED-40E5-4744-838A-D45DFA3C29B9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"08184384aa9f23ed1ef3f8ea4aea684a99dd2f35","datavalue":{"value":"The Floyd-Warshall algorithm [Flo62, Roy59, War62] is a classic dynamic programming algorithm to compute the length of all shortest paths between any two vertices in a graph (i.e. to solve the all-pairs shortest path problem, or APSP for short). Given a representation of the graph as a matrix of weights M, it computes another matrix M' which represents a graph with the same path lengths and contains the length of the shortest path between any two vertices i and j. This is only possible if the graph does not contain any negative cycles. However, in this case the Floyd-Warshall algorithm will detect the situation by calculating a negative diagonal entry. This entry includes a formalization of the algorithm and of these key properties. The algorithm is refined to an efficient imperative version using the Imperative Refinement Framework.","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361196$49634867-4A51-4EC2-92AA-0F9A45B4A7A6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"24b020801ec5e7b19d16baf8ec77b2baea503b33","datavalue":{"value":{"entity-type":"item","numeric-id":3267904,"id":"Q3267904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361196$4916F109-8521-45B7-841D-A5B9A0366CA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6315d9cda93162c2aba33a1d3e5ec00f12fd74a","datavalue":{"value":{"entity-type":"item","numeric-id":5729523,"id":"Q5729523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361196$B00610EA-3948-4A41-923E-66D36024FA77","rank":"normal"}],"P37":[{"mainsnak":{"snaktype":"value","property":"P37","hash":"9a21a8eebe97539644aa32b24dda137c12e751dc","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361196$F46E23B6-65EE-40F6-8445-65BB9678FCF4","rank":"normal"}],"P585":[{"mainsnak":{"snaktype":"value","property":"P585","hash":"6df1e1600a3acc40d1b0a9c9cf7cbc177462ddf9","datavalue":{"value":{"entity-type":"item","numeric-id":7361373,"id":"Q7361373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361196$A511D658-E8C8-46F2-878D-8F6D50648E37","rank":"normal"}],"P2651":[{"mainsnak":{"snaktype":"value","property":"P2651","hash":"0cb214ba14504ce52502380598f813a3d010fff5","datavalue":{"value":{"entity-type":"item","numeric-id":7360777,"id":"Q7360777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361196$3FD71F03-17A7-4D18-938C-B8879983E69C","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"908c3454b3659c4b140ccce33c5aee31081edc8d","datavalue":{"value":{"entity-type":"item","numeric-id":5976450,"id":"Q5976450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361196$8C9598A5-F3BF-4E20-8B69-61F49D92A481","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The Floyd-Warshall Algorithm for Shortest Paths","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_Floyd-Warshall_Algorithm_for_Shortest_Paths"}}}}}