### _QWOiNYUIVMPFSBKLiGSMAP_'s blog

By _QWOiNYUIVMPFSBKLiGSMAP_, history, 19 months ago, ,

What is the complexity of dijkstra algorithm but without the vis array and without checking for dist array code https://ideone.com/VTaE03

• 0

 » 19 months ago, # |   0 What's the meaning of k in the code?
•  » » 19 months ago, # ^ |   0 k is the total amount of money i have and each edge have cost and length cost is p and length is l
 » 19 months ago, # | ← Rev. 2 →   0 It can be quadratic, for example this directed graph:Initial node is connected with k nodes (with cost 1), these k nodes are connected with another node (middle)(with costs k, k — 1 , k — 2..., 1). Middle node is connected with another k nodes (with cost 1), which are connected to the final node (with cost oo, a.k.a. big enough). Certainly middle node will be visited k times, and visiting it requires k operations, as it has k neighbours. So total complexity would be at least .
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 If I understood the code correctly it wouldn't be difficult to construct O(2n) in a similar way.