there are many similar questions, but I haven't found direct answer to this question. Consider I have undirected, weighted graph with positive weights, no additional data - hence no heuristic (so it is not possible to use A*), is Dijkstra's algorithm with Fibonacci queue fastest known algorithm in terms of big-O notation? If so, is it proved it is fastest possible algorithm? Dijkstra's with Fibonacci queue is O(|E| + |V| * log |V|)


apparently Wikipedia answers my first part of the question:

This is asymptotically the fastest known single-source shortest-path algorithm for arbitrary directed graphs with unbounded non-negative weights

but do we know if it is fastest possible algorithm?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.