{"entities":{"Q1112733":{"pageid":1123482,"ns":120,"title":"Item:Q1112733","lastrevid":67032393,"modified":"2026-04-12T14:27:49Z","type":"item","id":"Q1112733","labels":{"en":{"language":"en","value":"A computational study of efficient shortest path algorithms"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4079187"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112733$6AA298C0-7DFC-43FF-857F-D51839D81CE0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5d6330d960dfd58eb289f8026504d1e80bfc91f6","datavalue":{"value":{"text":"A computational study of efficient shortest path algorithms","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1112733$95347035-BE36-408B-9CBD-CFA135349B7C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0027ca3922a99da5c3f44ad05f7c3af91aca901b","datavalue":{"value":"0659.90087","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112733$2DD37148-E9DA-4525-BC36-8393646CA05A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9da2916d3b7f0c59f733606adcc9adf0ca0bde5b","datavalue":{"value":"10.1016/0305-0548(88)90052-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112733$0C97B123-F6B5-4317-BEFF-485E8AA480C9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e26cee8ea2289e79e17078fe60a6bf7d2dc00c7c","datavalue":{"value":{"entity-type":"item","numeric-id":690021,"id":"Q690021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112733$EED296C3-9C8F-4536-9A60-CDFDEC9FB777","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c54a16030b0c395198d02e4efccf95861dbe12e7","datavalue":{"value":{"entity-type":"item","numeric-id":1093559,"id":"Q1093559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112733$62A01907-569B-4490-B321-1F620AAD8EF0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e630590c5ca6e787c3c7b5e291898405495fea2b","datavalue":{"value":{"entity-type":"item","numeric-id":162215,"id":"Q162215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112733$51A83C1D-0A5F-4E5E-87B7-5D543AE9E144","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1112733$AA25C4D8-2C90-4DC3-9C69-039F5C129AEE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5ce498a3e155968d87b5ce4b2d6123209fd62e2f","datavalue":{"value":"Five efficient shortest path algorithms are implemented and compared in this report. The selected algorithms are the most efficient, measured either in terms of worst case bounds or from previous computational studies. The algorithms include two using threshold functions, two using heaps, and one using buckets for sorting node labels. The last three algorithms have not been studied in detail before. The computational experiment employs a rigorous design to ensure that the results have statistical validity. Three different cost functions are generated to measure the sensitivity of each algorithm to cost distributions. Curve fittings are performed to summarize the results and they show high degrees of goodness-of-fit. The results reveal some heretofore unknown properties of some of the algorithms.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112733$5445A88D-F6F3-442C-BCD7-CA10916BAF26","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112733$B563D3BA-6E2F-4EA3-AC1F-AAAD3E00BD1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112733$B006F669-FF8C-4D76-8022-D9FD15C8D4CF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0c3cdf79c752d8ebfd03cf5cc0fe2a2330a68192","datavalue":{"value":"4079187","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112733$95BF32D2-4210-4667-8AB3-EEC4D0F03844","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f7da5df37c3497f803a47cb150aac87420e31076","datavalue":{"value":"computational comparisons","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112733$46E904BD-9E66-4E51-A4AB-FA969B224024","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9a11cb1e86b5af605acde3ead30df0469970ccfb","datavalue":{"value":"Five efficient shortest path algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112733$583B3EEC-3859-49C0-BB5A-66821570999E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f958f1f1caf56a0e3143111463ca67fa81df9aa5","datavalue":{"value":"threshold functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112733$0A887A24-83D0-4730-AA7D-CC3A8131E489","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4989eb152683ae59795f0e9b13db29659495b815","datavalue":{"value":"heaps","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112733$4AAC0C41-D715-4F5F-A138-1AC40A3862C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"56e2561bbf698bb33d2241f040dc30fbd4cbbc2b","datavalue":{"value":"sensitivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112733$8746A34E-2049-45AD-8E90-A0039452D537","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"69f3529b085b7f42b4a6d3fd4e8102dec9dd23a8","datavalue":{"value":"Curve fittings","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112733$7396ECEC-9D8F-4364-99EC-F6C10984581D","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"491b64eaf41e656c6938a9d968209d8ea37d3459","datavalue":{"value":{"entity-type":"item","numeric-id":41533,"id":"Q41533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112733$43FF162D-9156-4AE7-85EB-5C63A4A3A134","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112733$685D5B16-A848-4094-85B3-261DA29BB732","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"21239860e535ec88aef200df4476d8cdaa0d0b9a","datavalue":{"value":"https://doi.org/10.1016/0305-0548(88)90052-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1112733$7E4C30F7-DF88-4BA2-8CAC-464C737DFE29","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cb0baa5ae1a33d5fcb5b716aaf35923800b8c5db","datavalue":{"value":"W1968198624","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112733$F4576884-2688-4D3F-97C0-D8D42A699D10","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"242f6732c9aecb9180d76230dd0b3ce80be5a4cb","datavalue":{"value":{"entity-type":"item","numeric-id":4130999,"id":"Q4130999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112733$8845EF54-CB93-4D62-AB2E-0783C5CD4400","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc6e689ca9104617943bd76b284824e0c9ceb6bd","datavalue":{"value":{"entity-type":"item","numeric-id":3707420,"id":"Q3707420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112733$0C58043B-E635-4AF1-A1E5-442B2F045B8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d550175c8b76b88eeca0c90895d2993b32a403a","datavalue":{"value":{"entity-type":"item","numeric-id":5558804,"id":"Q5558804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112733$1666D2E3-17C5-436B-9DCC-07D3ECA6231E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9aceb326edfe9ced6aaa61bdb26a50f89dc1656","datavalue":{"value":{"entity-type":"item","numeric-id":3706872,"id":"Q3706872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112733$C9CA9812-B481-4513-B53A-7AF456545381","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e4f081355c6c90e1d82ff14f349b04b813218ae","datavalue":{"value":{"entity-type":"item","numeric-id":4111311,"id":"Q4111311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112733$86EC54AF-29D3-4A6C-88BE-C4A3FBE2DB63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06ee523fdbdf81d701feb6cd2239973cf706f45a","datavalue":{"value":{"entity-type":"item","numeric-id":4173214,"id":"Q4173214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112733$F5B62001-578B-4107-AF32-91863DCDE845","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4823f04d9fb1b5978ca3b1fa99933ee2850940a9","datavalue":{"value":{"entity-type":"item","numeric-id":3049827,"id":"Q3049827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112733$9C60CBCA-556F-46C0-880D-C23845137C79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49f4e19753fa33f0a8b7b019a0262f56bb60df14","datavalue":{"value":{"entity-type":"item","numeric-id":3750535,"id":"Q3750535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112733$27088FB3-AB55-4432-9618-685D90CCC7C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b989f45b85fa44137ad22092706b6102fd241bf","datavalue":{"value":{"entity-type":"item","numeric-id":78129,"id":"Q78129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112733$5F1104C2-938F-4601-9EAE-9FD0360AE1D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff81489e80366438468bf6dfe10c7a159bc3ea8c","datavalue":{"value":{"entity-type":"item","numeric-id":4057549,"id":"Q4057549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112733$A638924D-AC30-4F56-80E5-94E982A91CF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6704ccbb4c75ac5e07412c0181b63f464f1b7a0e","datavalue":{"value":{"entity-type":"item","numeric-id":5225293,"id":"Q5225293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112733$DCB020B8-0A18-49B3-B94C-8FE5EB6CA920","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2222e6e68cf5e0df7e4e5bfc0d92144d77fdc3b7","datavalue":{"value":{"entity-type":"item","numeric-id":3701214,"id":"Q3701214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112733$7E2975CD-4201-4721-9D6D-B4C5AA320AE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f41189633afecf9eedd15c9b48c7f2659788d2f2","datavalue":{"value":{"entity-type":"item","numeric-id":3951448,"id":"Q3951448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112733$21474097-BAC4-4C2E-B6D8-1CDA75CD7392","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e927c80db8e8c562bb886a822cc6867b7d56d1f","datavalue":{"value":{"entity-type":"item","numeric-id":3931440,"id":"Q3931440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112733$6C23C783-0B34-49CD-860F-2C1568E14FEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da5b18e5a44e3c67c75b0887be40e31fe6fc87d6","datavalue":{"value":{"entity-type":"item","numeric-id":4080986,"id":"Q4080986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112733$BD5BF185-4372-4FDA-965F-114E907DE84C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20fa1b666003daa16949e9befc519e1eaca7f719","datavalue":{"value":{"entity-type":"item","numeric-id":1088882,"id":"Q1088882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112733$A0C69336-1676-4F58-800D-AC31CDD79E57","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5dff206222ef722199573efce5e126181c34bd21","datavalue":{"value":{"entity-type":"item","numeric-id":3128914,"id":"Q3128914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e8ee38ca9791eb2f73d6a80e12a4b942c2e25ce9","datavalue":{"value":{"amount":"+0.8464596271514893","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1112733$20F7F05A-AB63-4E1A-99E4-4585154B5EF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c63b4f1c06c991171edf2273635cf671fe3db03","datavalue":{"value":{"entity-type":"item","numeric-id":1919099,"id":"Q1919099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9edfdaa5c98df84402c1606d367c42c3f12d4a22","datavalue":{"value":{"amount":"+0.8420727849006653","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1112733$849A5DED-8150-44BC-8D16-0A52B8E3E0FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1c7314725c3ad5c316974d81c820db282490969","datavalue":{"value":{"entity-type":"item","numeric-id":3315293,"id":"Q3315293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f68cecd55c26e478d20202dbe3ed650b64df3c4","datavalue":{"value":{"amount":"+0.8135589957237244","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1112733$17E51331-4588-4595-8B1D-A6DDD9C97053","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4685a7bcc3f7240d008163d5b4d357e8fbdf12ea","datavalue":{"value":{"entity-type":"item","numeric-id":5689632,"id":"Q5689632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c853b6252d69a2bd366c4f8dcb13dd55b110031","datavalue":{"value":{"amount":"+0.81088787317276","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1112733$78A7610B-0BD6-4D47-9E62-AEBE70280706","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3da7a6017dd4332177ee65f7f72c63beaeb1b68e","datavalue":{"value":{"entity-type":"item","numeric-id":4474117,"id":"Q4474117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28810af5845b6d69b596f03b71f851bdc67bafd7","datavalue":{"value":{"amount":"+0.8080147504806519","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1112733$700BB3A7-FCF2-4753-B206-50DA97C0F1C4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A computational study of efficient shortest path algorithms","badges":[]}}}}}