{"entities":{"Q511150":{"pageid":512917,"ns":120,"title":"Item:Q511150","lastrevid":42559296,"modified":"2025-07-03T09:28:30Z","type":"item","id":"Q511150","labels":{"en":{"language":"en","value":"Hybrid Bellman-Ford-Dijkstra algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6684588"}},"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":"Q511150$001BCD40-C7FE-4A76-8457-BE65A2EEC771","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"80a3b02971cb6046f3f8b7af3db54eb4f520e6f6","datavalue":{"value":{"text":"Hybrid Bellman-Ford-Dijkstra algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q511150$3E33988C-381D-4B0B-B43A-79DD0A318AD8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"87df46ce5f165bf0142aca8c134ab75289f87d1e","datavalue":{"value":"1364.05071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q511150$29C6EAC0-7D31-4D89-968E-75F608C8F06A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f3693b1afee621c36244f00002540aec7e474664","datavalue":{"value":{"entity-type":"item","numeric-id":511149,"id":"Q511149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q511150$11F659D2-A058-45B7-8836-B49834E41297","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"daef67eea74a7d97d05f1ea2c32e8f88b71d4c1e","datavalue":{"value":{"entity-type":"item","numeric-id":5615774,"id":"Q5615774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q511150$E3937060-72C2-4C2C-9D6E-52566DC4D6EB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"0a33251796f18919242eb286ef1f888e5d6e79da","datavalue":{"value":{"entity-type":"item","numeric-id":350720,"id":"Q350720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q511150$C22D8BE0-986C-445F-BCB9-10273C5BB20E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"db40ba1d53c33135c8dbe5d4d9cf42f70aa50a74","datavalue":{"value":{"time":"+2017-02-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q511150$2F47075E-A1AA-4FFB-AEE6-CD278637F4CC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f9cccf49da72ea8d7e969b33275ef38263faacb2","datavalue":{"value":"The paper considers the single-source shortest paths problem in a digraph with negative edge costs allowed. A new, hybrid algorithm for finding shortest paths from a source \\(s\\) in a graph \\(G\\) with general edge costs is constructed by combining Bellman-Ford and Dijkstra algorithms (hence BFD algorithm). It improves the running time bound of Bellman-Ford for graphs with a sparse distribution of negative cost edges.  This improvement is achieved by running Dijkstra at each Bellman-Ford round, without re-initializing values of distance function \\(d\\) at vertices. This is a legal implementation of Bellman-Ford, since Dijkstra is just a smart loop of relaxations. The authors prove the validity of this novel approach, despite the common knowledge: ``Dijkstra's algorithm cannot handle graphs with negative edge costs''. The bound for the number of BFD rounds is \\(k + 2\\), where \\(k\\) is the minimal integer such that for any vertex reachable from \\(s\\), there exists a shortest path from \\(s\\) to it containing at most \\(k\\) negative edges. The running time of a single BFD round is \\(O(|E| + |V| \\log |V |)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q511150$544C03B8-529A-4424-9859-9D8C56BD252A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d7f1127c63fcb04479eae252afd6f073fe30fe10","datavalue":{"value":{"entity-type":"item","numeric-id":187117,"id":"Q187117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q511150$20825723-C528-4BEF-88D7-569D2155C012","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q511150$FC8775A3-200E-488C-80D1-7ED20AAB697B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q511150$CECD4779-3C8A-4554-9D9A-6F76B9E1E4AA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"da3c4e379bd1ed0f0f4fbe3e7cb80a3f0e22d4a3","datavalue":{"value":"6684588","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q511150$46CDF56F-146C-4A1B-9236-6E2960B4F263","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a38b11968d7cb86be0842b661cd5bdd713115f5","datavalue":{"value":"graph algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q511150$13CBB8C6-B538-4F65-98FB-A52AC08D478C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f85e9f2721221f48af2e899508349c71e3faa29f","datavalue":{"value":"shortest path","type":"string"},"datatype":"string"},"type":"statement","id":"Q511150$518BEED3-4418-4D02-B90A-F9B898FE50CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"08a45f764c251dced79d0a16ec111590e33a5d24","datavalue":{"value":"negative edge","type":"string"},"datatype":"string"},"type":"statement","id":"Q511150$B4857BB7-2C51-4C05-A7EB-59CFFBADA0E4","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":"Q511150$4ABC9DA4-3EBC-4425-B331-FFC92BB23081","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":"Q511150$7F4E5E03-895C-4E28-B357-25B0DC77723B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"945a210ad40eb7b25a52e329e172a6bb2b82e291","datavalue":{"value":"https://doi.org/10.1016/j.jda.2017.01.001","type":"string"},"datatype":"url"},"type":"statement","id":"Q511150$D12F57DD-C59B-4425-BFC5-31CB255E3677","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5543315c7538ffdf74de07bb5914d2c193000f1c","datavalue":{"value":"W2570013196","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q511150$9267CEBE-90C1-4A30-8151-2342245EB8A0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d21da59a4c110362834b9928d5a01ac302c6dce","datavalue":{"value":{"entity-type":"item","numeric-id":5406231,"id":"Q5406231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q511150$193DACAA-C709-4DCC-86C5-3AA4C004B0EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60cf26ae066667600df09e7925abede5ecb143a2","datavalue":{"value":{"entity-type":"item","numeric-id":1762982,"id":"Q1762982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q511150$BD8CADDA-B47C-4F7B-BFA7-A562D9752B50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca46570134b3d969c3b0503c2166c451cf27b265","datavalue":{"value":{"entity-type":"item","numeric-id":5233514,"id":"Q5233514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q511150$3448532C-232A-4EB0-BAA8-8B2CECE0E72D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0780cc2d6ca73bce660833281d8171212204fa6","datavalue":{"value":{"entity-type":"item","numeric-id":4268713,"id":"Q4268713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q511150$AC9048F3-ECE0-4D75-99CE-39939DEE7FB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bffe48c7c76b90bf68970921698e19786e1600b","datavalue":{"value":{"entity-type":"item","numeric-id":2747613,"id":"Q2747613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q511150$6203EAC2-2ECE-4D7C-8D3A-39214E66080E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03a6c233404db069481557c925a57cc7e3b8e6b5","datavalue":{"value":{"entity-type":"item","numeric-id":834580,"id":"Q834580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q511150$34397A79-3FEA-4EDA-B946-BEC781A58712","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8aa35289747463c7264c9641cfbcb6f2612259c","datavalue":{"value":{"entity-type":"item","numeric-id":4842117,"id":"Q4842117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q511150$8C0FA4D5-0614-4E14-91B4-773A2C51E284","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b63a85f405aa43ed8f196d8f19adf30e62055e5","datavalue":{"value":{"entity-type":"item","numeric-id":5681531,"id":"Q5681531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q511150$69E13F64-8A8D-48B7-A579-16F714D56954","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f95a59cd2fec65f947d04915b0080d03411cdc1","datavalue":{"value":{"entity-type":"item","numeric-id":1240557,"id":"Q1240557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q511150$503E8D1C-232B-4799-B3EB-077E57986E87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23a21183b72da33bd49c7eab7d806c4d9e144f33","datavalue":{"value":{"entity-type":"item","numeric-id":4903793,"id":"Q4903793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q511150$80C7239E-20D8-4781-81C2-01FB9FB3A77F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00385ffca233881e14eacab77a70c639e02eb6f0","datavalue":{"value":{"entity-type":"item","numeric-id":5317203,"id":"Q5317203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q511150$8419A493-7400-44BC-B93C-DCF6CFF3BFEA","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":"Q511150$D2DFA976-167D-495B-A781-5975D61F5B2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57cc2dab6fcd00b3a5ef8504eceb52ca80db67db","datavalue":{"value":{"entity-type":"item","numeric-id":3158540,"id":"Q3158540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q511150$ED996CC5-1837-4912-AEA5-1B08D34D7646","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2503db959c96d4330ed8792a74314fb5b8ae2d7","datavalue":{"value":{"entity-type":"item","numeric-id":4091991,"id":"Q4091991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q511150$4132E0A1-E3A8-4D42-B9C5-E58E8C6D4AA8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d4444d677d3fc4ec4f88162c7be551df904fc939","datavalue":{"value":"10.1016/J.JDA.2017.01.001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q511150$C3C00B72-6E20-43DC-8D22-493363F1A082","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e7e126fbdfca3e90012fd3a7b5153ff9138727f8","datavalue":{"value":{"entity-type":"item","numeric-id":4229562,"id":"Q4229562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"57db6a6618505cf8c3ad229094f988223437dea4","datavalue":{"value":{"amount":"+0.8699124","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":"Q511150$626088EA-D7D0-4AF3-8640-063606C102B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b8c0b05c41371a61c68988699483884c2569f315","datavalue":{"value":{"entity-type":"item","numeric-id":266282,"id":"Q266282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2efb1b8d8f32da3dfbd17121bd537a92b20baf27","datavalue":{"value":{"amount":"+0.8401449","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":"Q511150$D6E449F0-5C90-40BD-B8B8-185BFDAC8BA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26edc1649959801b384c230edbe8496cd8ed9478","datavalue":{"value":{"entity-type":"item","numeric-id":2367969,"id":"Q2367969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f1d33fa0eced03a6bb50d3156e1811d616f070d","datavalue":{"value":{"amount":"+0.8396516","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":"Q511150$6A0C4BEF-6E80-49E0-99AD-B1EB427065CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97cbff631c4faa7ab61c8a01407dd8ea3255edf1","datavalue":{"value":{"entity-type":"item","numeric-id":336559,"id":"Q336559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2292fd9a4893f00fc1a9cce7889952cf6ffb00fc","datavalue":{"value":{"amount":"+0.8374667","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":"Q511150$E9047750-8B4C-43A5-9DC2-20B0EF0EF70E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70f565fcf2b6fec139b04433937658475f30c18b","datavalue":{"value":{"entity-type":"item","numeric-id":5194707,"id":"Q5194707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e4066ec9ed70273632c7da39b302bd9a32566a6","datavalue":{"value":{"amount":"+0.81580675","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":"Q511150$FFE239F8-7527-409D-B7D4-5E0E2EBECED7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0180ef7428fbdc3e84266316bd917ee75e2df656","datavalue":{"value":{"entity-type":"item","numeric-id":5260174,"id":"Q5260174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6310f7b2d46585eb40542494a744b2aab5c0f953","datavalue":{"value":{"amount":"+0.80767643","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":"Q511150$0FE9787D-1BB4-4347-9FAE-BCD6B44971DB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:511150","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:511150"}}}}}