Dijkstra linear running time on dense graph with Binary Heap
-
11-11-2019 - |
Question
First: The general running time of Dijkstras Shortest Path algorithm is
where m is the number of edges and n the number of vertices
Second: the number of expected decreasekey operations is the following
Third: The expected running time of dijkstra with a binary Heap which allows all operations in log(n) time is
But why is the running time on dense graphs linear if we consider a graph dense if
Can someone help with the O-notation and log calculations here?
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow