1
$\begingroup$

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|)

Edit:

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?

$\endgroup$
1

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.