{"entities":{"Q7361849":{"pageid":31521086,"ns":120,"title":"Item:Q7361849","lastrevid":105423911,"modified":"2026-10-08T13:45:48Z","type":"item","id":"Q7361849","labels":{"en":{"language":"en","value":"An Axiomatic Characterization of the Single-Source Shortest Path Problem"}},"descriptions":{"en":{"language":"en","value":"AFP entry ShortestPath"}},"aliases":{},"claims":{"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"dc3b5b88b5f9adc01a8ad7cce9fe7e98faaf5b64","datavalue":{"value":"https://isa-afp.org/entries/ShortestPath.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q7361849$18C29D81-CF6B-45BC-B890-DDEA3D761881","rank":"normal"}],"P43":[{"mainsnak":{"snaktype":"value","property":"P43","hash":"55b0fc3dc61297337ef172ccc1d73223c8496fb0","datavalue":{"value":"Christine Rizkallah","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361849$BB44946B-5BF6-4E11-AE0A-0B1025ADA51B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8f421bfdebcbc789883aafb200906997c2d98f28","datavalue":{"value":"This theory is split into two sections. In the first section, we give a formal proof that a well-known axiomatic characterization of the single-source shortest path problem is correct. Namely, we prove that in a directed graph with a non-negative cost function on the edges the single-source shortest path function is the only function that satisfies a set of four axioms. In the second section, we give a formal proof of the correctness of an axiomatic characterization of the single-source shortest path problem for directed graphs with general cost functions. The axioms here are more involved because we have to account for potential negative cycles in the graph. The axioms are summarized in three Isabelle locales.","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361849$4F365AAB-1C0C-4358-A0AE-E4AB48A181B2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2e4f78d53799d58c7c887f530c100a307e279033","datavalue":{"value":{"time":"+2013-05-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q7361849$4962F0AB-D713-467D-ABB4-C66F9A48B2F2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5c47e7f2a211a7fa5661f21f8af682ad973614be","datavalue":{"value":{"text":"An Axiomatic Characterization of the Single-Source Shortest Path Problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q7361849$CB9A7DA4-EFE6-4A6F-AD77-E540F2D79396","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":"Q7361849$A79FB51C-A12D-4477-9AC3-1E2ABE9947FF","rank":"normal"}],"P585":[{"mainsnak":{"snaktype":"value","property":"P585","hash":"b999678a517221bed9bd614caca8006ebca3a529","datavalue":{"value":{"entity-type":"item","numeric-id":7361796,"id":"Q7361796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361849$75454EE4-BAC6-4FDE-B0D8-4BF7CDDFF7AC","rank":"normal"}],"P2651":[{"mainsnak":{"snaktype":"value","property":"P2651","hash":"f3718ba60fb3ca54d1e75bc16696ddd7ca207e99","datavalue":{"value":{"entity-type":"item","numeric-id":7360827,"id":"Q7360827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361849$CBE8CC57-655C-4E1E-A7A1-87799D56D3B8","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":"Q7361849$30F672E1-9F39-47B3-9C38-6CC54A2CBA19","rank":"normal"}],"P13":[{"mainsnak":{"snaktype":"value","property":"P13","hash":"53af7f06675345c5b85833e6ad71ad0d071781c6","datavalue":{"value":"32236","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7361849$33EFB7AD-9AC4-4DAB-88E0-35C37006A296","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"acf10290b955a69659a681d98822944f91bbad9e","datavalue":{"value":"68","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7361849$205D44A8-A5C8-4766-8851-9F6015A09E24","rank":"normal"}],"P1458":[{"mainsnak":{"snaktype":"value","property":"P1458","hash":"ce995af0d54f8ab3594278c155d6ae4d6e3a6165","datavalue":{"value":{"entity-type":"item","numeric-id":16614,"id":"Q16614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361849$24A32CDC-267C-472B-8794-4153DC9C13B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"e600fcf4c16bf9bbec6afc7a64801eb6824b335c","datavalue":{"value":{"entity-type":"item","numeric-id":40264,"id":"Q40264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361849$C2CBC1A2-BF96-4251-87CB-2818356D409B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"1dd50e6d12db6d69b44d98a789719c63bc20b24d","datavalue":{"value":{"entity-type":"item","numeric-id":13265,"id":"Q13265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361849$130D1843-17FD-41B9-9717-1DD7B527BF6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"bb05cb23794774f62a8e4aa4de610af231973a1d","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361849$C9CFE05E-845A-4538-96F5-8A3BC406695E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"3e9c336168e17650e6c38b2eaa0f70237b2e636e","datavalue":{"value":{"entity-type":"item","numeric-id":40295,"id":"Q40295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361849$1504C381-09AB-40AA-838B-1680757CD66E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"9f05f47ffa49231241d775f50bc98a9e3449e1f6","datavalue":{"value":{"entity-type":"item","numeric-id":41246,"id":"Q41246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361849$68603FEC-9A95-4B41-9B51-466E83F482F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"61d0c0612cc30c9c51b93ddaf1f78ee1ae75f9fe","datavalue":{"value":{"entity-type":"item","numeric-id":18676,"id":"Q18676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361849$57D5B247-B5F9-4D8B-9E80-CCB5E99EEEF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"cc4eff68b160f30b8d66dfcb610a0ea7a927079b","datavalue":{"value":{"entity-type":"item","numeric-id":17039,"id":"Q17039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361849$DDA9A979-83C4-4198-B8C0-0A599AB1A224","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"cc41d9364226bfa8139f8dbc43b1b77967245f13","datavalue":{"value":{"entity-type":"item","numeric-id":17631,"id":"Q17631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361849$DDD394EA-45A8-4D85-A6BB-7A0C0E9D59C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"a78d10351f0710c61eb19af8201147471568ba3a","datavalue":{"value":{"entity-type":"item","numeric-id":16796,"id":"Q16796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361849$9979D07B-B55E-476F-BB19-27CABD6ED9B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"07eb0f28b45c8f9b5cf112bbf02e95717fb938ca","datavalue":{"value":{"entity-type":"item","numeric-id":25202,"id":"Q25202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361849$2E7301D8-FC75-4F05-8D61-194C45AFF33B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"4d7f4b76492a75780585d40fb718d00d42a05322","datavalue":{"value":{"entity-type":"item","numeric-id":19570,"id":"Q19570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361849$58619C20-DC4B-4B72-B28D-A944120AA1B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"1286389c58ecdb69c422604e3e1f0dbe5e0370f0","datavalue":{"value":{"entity-type":"item","numeric-id":15691,"id":"Q15691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361849$69682300-6A74-4C8A-8F79-05F62D23BE02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"144f0221487b5ba035abaca0f440960a9e47efeb","datavalue":{"value":{"entity-type":"item","numeric-id":27113,"id":"Q27113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361849$17BE7BE1-F475-477D-B1A0-5B630611579B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"e3e9bb7b329ec8e71fcb8b28c9805dd4509dedab","datavalue":{"value":{"entity-type":"item","numeric-id":19731,"id":"Q19731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361849$DED275C4-A826-4E62-8E02-C389D3C877FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"bb0bb7298ee3f535da596bef22c2f5c7449c7dc4","datavalue":{"value":{"entity-type":"item","numeric-id":19271,"id":"Q19271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361849$C032BE45-3C2E-4CD6-846D-03F8E58767B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"a2a767ccd0e9bdc5b1b4a2069a6679f9340a857a","datavalue":{"value":{"entity-type":"item","numeric-id":14275,"id":"Q14275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361849$BAFEDAEB-E78A-4D4A-BFFD-B9801EEFD019","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"ff80b41d03c65073c007c903a317be0a9c94293e","datavalue":{"value":{"entity-type":"item","numeric-id":13958,"id":"Q13958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361849$94D262DF-2247-432E-AB87-5472A65C3DC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"ecda3e6d8e971c0b93d4cf3afb41990e853f830f","datavalue":{"value":{"entity-type":"item","numeric-id":13212,"id":"Q13212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361849$EEC8B641-250C-43C7-A528-001F4E44E008","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"d598055e76e7c072cae9308bcd9069cd8e8780d2","datavalue":{"value":{"entity-type":"item","numeric-id":13169,"id":"Q13169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361849$8A9E0439-A25F-40A3-90A6-E6987713EFDD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An Axiomatic Characterization of the Single-Source Shortest Path Problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_Axiomatic_Characterization_of_the_Single-Source_Shortest_Path_Problem"}}}}}