{"entities":{"Q912765":{"pageid":914613,"ns":120,"title":"Item:Q912765","lastrevid":65302755,"modified":"2026-04-12T01:39:35Z","type":"item","id":"Q912765","labels":{"en":{"language":"en","value":"The quickest path problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4145685"}},"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":"Q912765$0209FF52-56AC-49B2-8B94-C75EC36C9DD2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1588725cf711ffbee726c72f4cd9209aaf032dd1","datavalue":{"value":{"text":"The quickest path problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q912765$174888D7-9B37-4DFD-AAE3-2245C39A637C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a6a7e5f5544c9fbebccd620a335ff885654606ae","datavalue":{"value":"0698.90083","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q912765$C624FDC0-C6A6-4B18-AD2E-30C85375CCBE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e976b6a3bc59d7dc1bec26adb1303b66cbe4a14d","datavalue":{"value":"10.1016/0305-0548(90)90039-A","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q912765$3CDB2A61-0707-4E98-93E1-94EFC68BCA9C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c5832f8876614de1887b6fff71a1066143db327e","datavalue":{"value":{"entity-type":"item","numeric-id":786129,"id":"Q786129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q912765$45EF5870-B2E9-4F46-8251-123579E9BC2B","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":"Q912765$69BA6C96-6645-4542-B996-699EDD897B2E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q912765$D38542FB-C98B-44F2-AE7D-5B05D3832F53","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"37661c8ef6d6340df0d035d33ea642d65536d5d6","datavalue":{"value":"The authors consider the following modification of shortest path problems: let a digraph with n nodes and m arcs be given. For any arc (u,v) we have its lead time l(u,v) and its capacity c(u,v). The transmission time for \\(\\sigma\\) units of data along this arc is defined as \\(t(u,v):=l(u,v)+\\sigma /c(u,v)\\). The quickest path problem asks for a path from the source to the sink along which the sum of transmission times is minimum. For fixed \\(\\sigma\\), the authors state an algorithm of time complexity \\(O(m^ 2+mn \\log m)\\) to solve the quickest path problem. If a quickest path for any arbitrary \\(\\sigma\\) is looked for, then the network can be preprocessed in \\(O(m^ 2+mn \\log m)\\) time such that finding a quickest path requires only O(log m) additional steps.","type":"string"},"datatype":"string"},"type":"statement","id":"Q912765$8CED4D81-F237-49CE-A452-ACE42B739E3A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q912765$EDA36CF5-3F50-4D28-8075-F0F8BB46C2B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q912765$88C8268F-3D48-42C3-AA58-276C0E50BCD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q912765$87FFCEED-8474-4373-BD32-CA88C5FB54E1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"80cc50d4e01e69fe721bc980a78013c68387568d","datavalue":{"value":"4145685","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q912765$03C4C6D7-49EE-405B-BEBA-61D02BBAC1D7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f85e9f2721221f48af2e899508349c71e3faa29f","datavalue":{"value":"shortest path","type":"string"},"datatype":"string"},"type":"statement","id":"Q912765$CD20263A-BBB9-4501-9A50-4B769ACB7452","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85eef5242ed0d57acc9caf7d48d82888e646d12f","datavalue":{"value":"digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q912765$9C717611-E6E0-4CED-96A3-48857511B9D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8563e46287f5a4e0b0c44c064cf3916ba452e3d8","datavalue":{"value":"quickest path","type":"string"},"datatype":"string"},"type":"statement","id":"Q912765$865FCFB1-F519-4542-9BC6-D25C1BA20912","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3b6e891f06c81591be5bbe33284800abc7dac18","datavalue":{"value":"transmission times","type":"string"},"datatype":"string"},"type":"statement","id":"Q912765$D503449C-21E5-4896-81F3-775994758447","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4a45374906fa7445234d8f571198ca1750e8882a","datavalue":{"value":{"entity-type":"item","numeric-id":170644,"id":"Q170644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q912765$BADFD6BE-41ED-44CB-93C9-44B83E59B0C3","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":"Q912765$D2E41BCB-94A2-4101-8796-7804FA58FC8C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"00bf1c7145d7b993d82e6bcc4d16af477850663b","datavalue":{"value":{"entity-type":"item","numeric-id":1102209,"id":"Q1102209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q912765$361D89F3-4DBC-4277-A1E7-C339261EC6FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0cf9dfbab1986c3d9cea81d8308ec7cb5e10e77e","datavalue":{"value":{"entity-type":"item","numeric-id":3330993,"id":"Q3330993"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q912765$67EFA3A9-55BF-4F40-A601-C00FDB726FF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68bfa0b16fb1a6b17c0ab9a864711044aab28d34","datavalue":{"value":{"entity-type":"item","numeric-id":4136979,"id":"Q4136979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q912765$E0EB2F05-D4B8-45AC-97DB-5AE48D51E5CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bcb677c00c82d8a57f649155806a4b1b334c7199","datavalue":{"value":{"entity-type":"item","numeric-id":4065317,"id":"Q4065317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q912765$6902E3E2-69E8-4903-8AE5-DB92B40AC76B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f879f118d39e858978a1451bfc36c1747e956157","datavalue":{"value":{"entity-type":"item","numeric-id":4742310,"id":"Q4742310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q912765$11CF88A0-0212-4093-B7DE-329744D9E940","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":"Q912765$B91FB5D0-51EC-4CB4-B50D-7E75B4AD6451","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"aa412d7975188fd424cd643c03e46688b4cd080d","datavalue":{"value":"https://doi.org/10.1016/0305-0548(90)90039-a","type":"string"},"datatype":"url"},"type":"statement","id":"Q912765$DA093EA0-F410-4C5F-9A79-D32D809E051D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e687b7d53bd79f8870e210cf9adcf5653770f59b","datavalue":{"value":"W1994909604","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q912765$51A7FE44-2C79-4C4F-97F0-4743E3EDA5DC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63b91a0b2f3e222af6566fe1aedfb6c204fa9347","datavalue":{"value":{"entity-type":"item","numeric-id":1261485,"id":"Q1261485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cabbbbbb22ffc410c7a299bddc9f93c332ce58e2","datavalue":{"value":{"amount":"+0.96564674","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":"Q912765$52287D76-8572-4D9D-948F-38BAEA573CDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2499e7e44a8c74e0a3a7d420c3edf3f61a79fb3c","datavalue":{"value":{"entity-type":"item","numeric-id":1362526,"id":"Q1362526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f7c675abec01cfb76db6fb20607faccf45b0fe1a","datavalue":{"value":{"amount":"+0.9208034","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":"Q912765$7CE9F962-2EF8-43DA-BBBB-CD42DECF42A6","rank":"normal"},{"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":"197ce41c1ff37a915cbbba2c60746b8ceecdacb7","datavalue":{"value":{"amount":"+0.9088289","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":"Q912765$64CB682A-C0EB-4870-9114-AFEB631A6BA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2bc897265510f291a884b80bd03f005ea19bf01d","datavalue":{"value":{"entity-type":"item","numeric-id":2785406,"id":"Q2785406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e30b858df20cd138c5a015de7a6689fc07fa7330","datavalue":{"value":{"amount":"+0.8997166","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":"Q912765$6D342CDF-FFAF-42CD-8527-31D94F1E6D34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5524875c8848f57fbe98698b987b9862c1a53545","datavalue":{"value":{"entity-type":"item","numeric-id":5326774,"id":"Q5326774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e61cf88d8c8d0ede967adc8f4980341fdb7f863c","datavalue":{"value":{"amount":"+0.8944094","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":"Q912765$C37C098B-27A7-46A6-94C0-F6222D6E11F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a625629411b93599f0581315af6b649811ac342","datavalue":{"value":{"entity-type":"item","numeric-id":1676484,"id":"Q1676484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"184d1d8355a8776321cce59d9fa3a19b57fc3d2e","datavalue":{"value":{"amount":"+0.88275737","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":"Q912765$B0D75F16-2253-47B5-908F-19BE8874EBF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f3b829490ceaafc83ec171d0dacc5996d01d5c7","datavalue":{"value":{"entity-type":"item","numeric-id":2356016,"id":"Q2356016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b8453e8ce1ff9878cd356b6cf0bda7372085c2d8","datavalue":{"value":{"amount":"+0.88185054","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":"Q912765$07432BA8-F1C8-4489-BB07-99B47BC5C4BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de088b110cb3511adaa3584e554ce162864b9773","datavalue":{"value":{"entity-type":"item","numeric-id":1184451,"id":"Q1184451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"241fa0c4a5ff91db325bc7c1a90d477cdd05c5d0","datavalue":{"value":{"amount":"+0.88077116","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":"Q912765$13D320D0-5785-4C61-A16D-8EF724D9D15D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"673084de838513ce98e713576c58b3e650117aeb","datavalue":{"value":{"entity-type":"item","numeric-id":1272178,"id":"Q1272178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be36b9350b0815d5b763f69595eeb34a90ffca4c","datavalue":{"value":{"amount":"+0.8791717","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":"Q912765$7CC8EC6F-17C5-46A6-82FE-E43BA1990EE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b64603bb71f8b322d388837960474120f70b3f86","datavalue":{"value":{"entity-type":"item","numeric-id":337093,"id":"Q337093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3654c3fb3baa3828f676b391a703a76dfa7c5a24","datavalue":{"value":{"amount":"+0.87813294","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":"Q912765$6F3D977D-660D-45DE-B6CD-986403738FE2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The quickest path problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_quickest_path_problem"}}}}}