{"?xml":{"@version":"1.0"},"edm:RDF":{"@xmlns:dc":"http://purl.org/dc/elements/1.1/","@xmlns:edm":"http://www.europeana.eu/schemas/edm/","@xmlns:wgs84_pos":"http://www.w3.org/2003/01/geo/wgs84_pos","@xmlns:foaf":"http://xmlns.com/foaf/0.1/","@xmlns:rdaGr2":"http://rdvocab.info/ElementsGr2","@xmlns:oai":"http://www.openarchives.org/OAI/2.0/","@xmlns:owl":"http://www.w3.org/2002/07/owl#","@xmlns:rdf":"http://www.w3.org/1999/02/22-rdf-syntax-ns#","@xmlns:ore":"http://www.openarchives.org/ore/terms/","@xmlns:skos":"http://www.w3.org/2004/02/skos/core#","@xmlns:dcterms":"http://purl.org/dc/terms/","edm:WebResource":[{"@rdf:about":"http://www.dlib.si/stream/URN:NBN:SI:doc-9OFEH90W/08f60c3e-07ab-4af3-8bc8-5ae4a5d143c1/PDF","dcterms:extent":"485 KB"},{"@rdf:about":"http://www.dlib.si/stream/URN:NBN:SI:doc-9OFEH90W/ca66cc4c-c8de-4ea2-94b1-0f9cb12fe683/TEXT","dcterms:extent":"53 KB"}],"edm:TimeSpan":{"@rdf:about":"2008-2025","edm:begin":{"@xml:lang":"en","#text":"2008"},"edm:end":{"@xml:lang":"en","#text":"2025"}},"edm:ProvidedCHO":{"@rdf:about":"URN:NBN:SI:doc-9OFEH90W","dcterms:isPartOf":[{"@rdf:resource":"https://www.dlib.si/details/URN:NBN:SI:spr-UP1WMFAR"},{"@xml:lang":"sl","#text":"Ars mathematica contemporanea"}],"dcterms:issued":"2022","dc:creator":["Brodnik, Andrej","Grgurovič, Marko","Požar, Rok"],"dc:format":[{"@xml:lang":"sl","#text":"številka:1"},{"@xml:lang":"sl","#text":"letnik:22"},{"@xml:lang":"sl","#text":"P1.01 (str. 1-22)"}],"dc:identifier":["DOI:10.26493/1855-3974.2467.497","ISSN:1855-3966","COBISSID_HOST:61578243","URN:URN:NBN:SI:doc-9OFEH90W"],"dc:language":"en","dc:publisher":{"@xml:lang":"sl","#text":"Univerza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologije"},"dc:subject":[{"@xml:lang":"sl","#text":"all-pairs shortest paths"},{"@xml:lang":"sl","#text":"Floyd-Warshall algorithm"},{"@xml:lang":"sl","#text":"Floyd-Warshallov algoritem"},{"@xml:lang":"sl","#text":"najkrajše poti med vsemi pari vozlišč"},{"@xml:lang":"sl","#text":"probabilistic analysis"},{"@xml:lang":"sl","#text":"verjetnostna analiza"}],"dcterms:temporal":{"@rdf:resource":"2008-2025"},"dc:title":{"@xml:lang":"sl","#text":"Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time|"},"dc:description":[{"@xml:lang":"sl","#text":"The paper describes two relatively simple modifications of the well-known Floyd-Warshall algorithm for computing all-pairs shortest paths. A fundamental difference of both modifications in comparison to the Floyd-Warshall algorithm is that the relaxation is done in a smart way. We show that the expected-case time complexity of both algorithms is ?$O(n^2\\log^2 n)$? for the class of complete directed graphs on ?$n$? vertices with arc weights selected independently at random from the uniform distribution on ?$0,1$?. Theoretically best known algorithms for this class of graphs are all based on Dijkstra's algorithm and obtain a better expected-case bound. However, by conducting an empirical evaluation we prove that our algorithms are at least competitive in practice with best know algorithms and, moreover, outperform most of them. The reason for the practical efficiency of the presented algorithms is the absence of use of priority queue"},{"@xml:lang":"sl","#text":"V članku sta opisani dve relativno preprosti spremembi dobro znanega Floyd-Warshallovega algoritma za izračun najkrajših poti med vsemi pari vozlišč. Bistvena razlika obeh sprememb v primerjavi s Floyd-Warshallovim algoritmom je v tem, da se sproščanje izvede na pameten način. Pokažemo, da je pričakovana časovna zahtevnost obeh algoritmov ?$O(n^2\\log^2 n)$? za razred polnih usmerjenih grafov na ?$n$? vozliščih, pri čemer so uteži na povezavah izbrane neodvisno z vrednostmi enakomerno porazdeljene naključne spremenljivke na intervalu ?$0,1$? Teoretično najboljši algoritmi za ta razred grafov temeljijo na Dijkstrovem algoritmu in dosežejo boljšo mejo v pričakovanem primeru. Kljub temu z empiričnim ovrednotenjem pokažemo, da sta naša algoritma v praksi vsaj konkurenčna z najbolj znanimi algoritmi in poleg tega prekašata večino od njih. Razlog za praktično učinkovitost predstavljenih algoritmov je odsotnost uporabe vrste s prednostjo"}],"edm:type":"TEXT","dc:type":[{"@xml:lang":"sl","#text":"znanstveno časopisje"},{"@xml:lang":"en","#text":"journals"},{"@rdf:resource":"http://www.wikidata.org/entity/Q361785"}]},"ore:Aggregation":{"@rdf:about":"http://www.dlib.si/?URN=URN:NBN:SI:doc-9OFEH90W","edm:aggregatedCHO":{"@rdf:resource":"URN:NBN:SI:doc-9OFEH90W"},"edm:isShownBy":{"@rdf:resource":"http://www.dlib.si/stream/URN:NBN:SI:doc-9OFEH90W/08f60c3e-07ab-4af3-8bc8-5ae4a5d143c1/PDF"},"edm:rights":{"@rdf:resource":"http://creativecommons.org/licenses/by/4.0/"},"edm:provider":"Slovenian National E-content Aggregator","edm:intermediateProvider":{"@xml:lang":"en","#text":"National and University Library of Slovenia"},"edm:dataProvider":{"@xml:lang":"sl","#text":"Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije"},"edm:object":{"@rdf:resource":"http://www.dlib.si/streamdb/URN:NBN:SI:doc-9OFEH90W/maxi/edm"},"edm:isShownAt":{"@rdf:resource":"http://www.dlib.si/details/URN:NBN:SI:doc-9OFEH90W"}}}}