What is the worst case running time of dijikstras algorithm when implemented with d heaps?

Answer 1

The worst-case running time of Dijkstra's algorithm when implemented with d-ary heaps is (O((V + E) \log_d V)), where (V) is the number of vertices and (E) is the number of edges. This complexity arises because each vertex can be extracted from the heap, and the decrease-key operation can be performed for each edge. The logarithmic factor is based on the d-ary heap's height, which is (O(\log_d V)). Thus, using a d-ary heap can be more efficient than using a binary heap, especially when d is larger.