Problem statement

Complexity Analysis : 

MNP maintains a priority queue Q, which stores the nodes together with their 

cost and parent. Let N denote the number of nodes which must change their cost 

or parent attributes (or both), M be the number of links that may cause any node 

in the queue to change its cost (which is performed by the decreasekey 

operation of the priority queue). Let enQ be the time needed by ENQUEUE to 

enqueue a node, exQ be the time needed by EXTRACTMIN to extract the node, 

and dkQ be the time needed by ENQUEUE (decrease-key) to update a node 

which is existing in the queue.