{"entities":{"Q794155":{"pageid":796003,"ns":120,"title":"Item:Q794155","lastrevid":42698010,"modified":"2025-07-08T14:27:10Z","type":"item","id":"Q794155","labels":{"en":{"language":"en","value":"A priority queue for the all pairs shortest path problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3858397"}},"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":"Q794155$6D1A4EFA-8BCA-409E-ACA3-BADCC5D622B3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9ada496f9f3692801b01f110f112b1d8a2cfd503","datavalue":{"value":{"text":"A priority queue for the all pairs shortest path problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q794155$6EE4CB93-6CA9-4368-82B8-3BBF5FA270AA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0d4c3ac57b07f88ec9772da460d88d3b9a507d26","datavalue":{"value":"0539.68022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794155$5E3E8D52-5863-49E1-8B92-8276C69C6DCF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"518e00732ea5bccdb6e3b2b61db0b816591912d5","datavalue":{"value":"10.1016/0020-0190(84)90109-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794155$EA6C950A-785E-4534-8B73-19D036C7D5FC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a1e87efb34de958c0b6dd10db1d36166d45a6529","datavalue":{"value":{"entity-type":"item","numeric-id":293391,"id":"Q293391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794155$3C56633B-C820-48BA-91AD-4540D0E107EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fbd8d347166af77436aa4bae89e2c3259d9425c5","datavalue":{"value":{"entity-type":"item","numeric-id":350722,"id":"Q350722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794155$7B4EA172-5438-417A-8AB5-C9414A11B088","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794155$7CE2B400-8476-41F5-821E-857038A56BBB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q794155$306B6E41-4B1F-44EC-86F3-F26287459FDC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b78c90db4980d63714b21d43df0de1d904be4de3","datavalue":{"value":"A linked list priority queue data structure is given that in some situations out performs, in terms of comparisons amongst elements in the data structure, existing priority queue structures such as the heap. It is shown that this new queue structure is suitable for use with \\textit{E. W. Dijkstra's} shortest path algorithm [Numer. Math. 1, 269-271 (1959; Zbl 0092.160)] with the combination yielding an algorithm for the all pairs shortest path problem that on a dense graph of n vertices requires \\(n^ 3+O(n^{2.5})\\) operations on path costs. In a computational framework where addition and comparison are the only operations permitted on path costs, this slightly improves \\textit{J. Y. Yen's} bound [J. Assoc. Comput. Mach. 19, 423-424 (1972; Zbl 0242.94028)] of \\((3/2)n^ 3\\) operations.","type":"string"},"datatype":"string"},"type":"statement","id":"Q794155$C1CED54F-931B-497F-B661-73CD3BF0BE68","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9ed1e3c6cced595a05b8ae19055521b22405b78a","datavalue":{"value":"68W99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794155$741CEA8B-91AD-4B5E-9BF7-53FF5DCD9575","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794155$F5C131A9-D516-462A-B988-366813C85A5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794155$873E6B0B-50BD-4C5C-8177-AA9930BFD980","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794155$FF5288AD-628E-4EC1-AB7A-0238B2C99ECA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"74d0c94dc42cd1c2ba8ac5530d79c4f4ea63e044","datavalue":{"value":"3858397","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794155$D783B03F-0C16-4452-97DF-A7E164594573","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90bc349d6d55eb8026148892e900ce256ffdd986","datavalue":{"value":"analysis of algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q794155$A2B76E87-4F20-4377-8325-877300B816F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d949366ba9469e2b4b8fde783d53948a2494379","datavalue":{"value":"linked list priority queue data structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q794155$164A43E7-2C03-4623-AD5F-1BAA7FEF1D0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"971fe2895bae2a51e52612ff265d7496f3bd3165","datavalue":{"value":"shortest path algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q794155$4C98D164-5E54-4787-A75B-1989147E1499","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"1412ceb6c71a23f10e8f7e008bf034264afa1496","datavalue":{"value":{"entity-type":"item","numeric-id":41444,"id":"Q41444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794155$422148F5-7E09-42AD-9F92-A53D12C9F1A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"40511068b347a60aa196b665fa4c4acc6f9d4e19","datavalue":{"value":{"entity-type":"item","numeric-id":46612,"id":"Q46612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794155$1FB65688-AE80-49A8-9A82-C924AFF7D8B9","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":"Q794155$BA731280-F803-4002-973D-BB2A07B4BD30","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"47b48058c41ab6faa391490c1a62c4d63e3ac266","datavalue":{"value":"https://doi.org/10.1016/0020-0190(84)90109-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q794155$19D07823-4AD1-40A8-AEC8-C4E1181CEB20","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"aa4924225a2348e7f1d75899276571acf332d57f","datavalue":{"value":"W1991351021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794155$A4F9093E-47F2-486C-AFDF-9C66247752E7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd3a7cfeece8562a9ac87120b107e2b528967937","datavalue":{"value":{"entity-type":"item","numeric-id":4773298,"id":"Q4773298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794155$C8C22F72-6F2A-44D8-8F77-A0388E47A5C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc2302c1ac47a727b38c9a44769d5fcfbae13085","datavalue":{"value":{"entity-type":"item","numeric-id":3670595,"id":"Q3670595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794155$D8212E36-5A6F-4D6F-B3B0-3FA8BD601283","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":"Q794155$9828B16E-414E-41A4-BCB6-F4E785089DDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14acfe2f4f339610911d7bf217920bda5474651c","datavalue":{"value":{"entity-type":"item","numeric-id":4091447,"id":"Q4091447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794155$ACB912CC-2855-4870-81DC-26DD6169F607","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b158744ba9d998b8e423d88d9050bc108f9d0760","datavalue":{"value":{"entity-type":"item","numeric-id":5656786,"id":"Q5656786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794155$665013AE-D388-4D23-B3F3-9F8EC70829BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0fe64530757d8f3ef9c2940f48424a694c90c2fd","datavalue":{"value":{"entity-type":"item","numeric-id":1222511,"id":"Q1222511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794155$5D379E42-15B0-4DDE-A75C-A10F39280795","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8881f2b8f68c7e0bb09169650cf67ac057b998ec","datavalue":{"value":{"entity-type":"item","numeric-id":1158968,"id":"Q1158968"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794155$30F4159C-E987-403A-84C9-344AE46E1A21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dad0037d127c13d7455329129a8da84d6251d9cd","datavalue":{"value":{"entity-type":"item","numeric-id":1149782,"id":"Q1149782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794155$13D294A3-A4C6-407B-A6B0-6ADD709195C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bfa111708107f38db5b38bd20d9da2aed453dead","datavalue":{"value":{"entity-type":"item","numeric-id":5668831,"id":"Q5668831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794155$65F960EF-F8E0-4185-8020-341D75DFE98B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"362310385babf2c6e7dc09fc465b15d7394c796b","datavalue":{"value":{"entity-type":"item","numeric-id":3893329,"id":"Q3893329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794155$38F0ABA2-26D6-4088-91BF-8B0C983EAC3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"765ad3bf3457debbdec24c9e8245994cefae834f","datavalue":{"value":{"entity-type":"item","numeric-id":5653927,"id":"Q5653927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794155$DF75FFED-E728-4E3E-B220-6C9963AA899A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be3624bcabb24cc9ff70e76200fbb9cd084e9cdc","datavalue":{"value":{"entity-type":"item","numeric-id":1228358,"id":"Q1228358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794155$6FD66B9B-677A-4A78-8315-1C252C99CAF9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2b4136c6194f2c54876652e59b953c70c273f4d","datavalue":{"value":{"entity-type":"item","numeric-id":2366074,"id":"Q2366074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a4b05b809c0d3f6f5d1afafbe2da8321d28613e","datavalue":{"value":{"amount":"+0.8934712","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q794155$B1D5606F-4361-4306-A571-F8628C273592","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97e75cba62598c72189816093aca4d7657e00217","datavalue":{"value":{"entity-type":"item","numeric-id":4681187,"id":"Q4681187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7ca0d809db3598c04278ca3a279ac1cc2a8db9cd","datavalue":{"value":{"amount":"+0.89301014","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q794155$20B4D2B6-2464-45DA-B943-841E2EFADA7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"03755f86140099f40b768f527d7a8b34321d94ad","datavalue":{"value":{"entity-type":"item","numeric-id":5289052,"id":"Q5289052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e41b88ed433137c236aab2b0acdd4df3ec6b42c0","datavalue":{"value":{"amount":"+0.8916985","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q794155$F3CFF934-F3F9-4D65-84BE-3EE2CC903B69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1739d04f228aba655588e0e659a3d68123dab144","datavalue":{"value":{"entity-type":"item","numeric-id":6069155,"id":"Q6069155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bdff4d6de4c8abaa4a4b486eba6dd8007ff62efa","datavalue":{"value":{"amount":"+0.8821908","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q794155$F0DD2079-F431-45C5-A6E0-F523AD426013","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"034ef131be10196857b67487dcc8a56ba0cc3abc","datavalue":{"value":{"entity-type":"item","numeric-id":5874311,"id":"Q5874311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bdff4d6de4c8abaa4a4b486eba6dd8007ff62efa","datavalue":{"value":{"amount":"+0.8821908","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q794155$AEADA067-3F9F-4CD3-B90D-8AEB99FED64B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54d2303e6dff433d48b7126cec1f5329f4b4fb0b","datavalue":{"value":{"entity-type":"item","numeric-id":4943891,"id":"Q4943891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c9cc2623779267870a75287dea107cde1436991c","datavalue":{"value":{"amount":"+0.8801122","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q794155$7CD3EC35-ADE4-4EC5-96E3-D9B24AF7B82C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01371b784b157d7521fee86d2243fb9c0023fc47","datavalue":{"value":{"entity-type":"item","numeric-id":875428,"id":"Q875428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c618a83427cd165b204f9a07e1b6199e34edf670","datavalue":{"value":{"amount":"+0.87861073","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q794155$2A66CD40-3AD1-4079-89FB-A3A2AF641D05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eb37a9a2bd4bb883f45fa25058d4d4161f04ba6e","datavalue":{"value":{"entity-type":"item","numeric-id":3581293,"id":"Q3581293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f0339d5e7f3fc8d44cf53d809c8134da6ed1f65","datavalue":{"value":{"amount":"+0.87854356","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q794155$99EBEE48-41D3-43A6-B9F5-FF4523B449C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"056982490b9b78acc8595d884f2d758a8eef1a81","datavalue":{"value":{"entity-type":"item","numeric-id":5212359,"id":"Q5212359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0deef4acd48f60c4382c510faeb68f847c99f3a5","datavalue":{"value":{"amount":"+0.8778938","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q794155$B87E0C0D-05E6-4543-9688-2F67F476F481","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:794155","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:794155"}}}}}