I'm trying to implement Prim's Algorithm and for that I need to have a decreaseKey method for a priority queue (to update the key value in a priority queue). Can I implement this in the STL Priority Queue?

If it helps, this is the algorithm I'm following:

for each vertex u in graph G

set key of u to INFINITY

set parent of u to NIL

set key of source vertex to 0

en-queue to priority queue Q all vertices in graph

While Q is not empty

extract vertex u from Q // u is vertex with lowest key in Q

for each adjacent vertex v of u do if (v is still in Q) and (weight-function(u, v) < key of v) then

set u to be parent of v

update v's key to equal weight-function(u, v) //This part is giving me problems as I don't know how implement decreaseKey in priority queue

If it helps, this is the algorithm I'm following:

for each vertex u in graph G

set key of u to INFINITY

set parent of u to NIL

set key of source vertex to 0

en-queue to priority queue Q all vertices in graph

While Q is not empty

extract vertex u from Q // u is vertex with lowest key in Q

for each adjacent vertex v of u do if (v is still in Q) and (weight-function(u, v) < key of v) then

set u to be parent of v

update v's key to equal weight-function(u, v) //This part is giving me problems as I don't know how implement decreaseKey in priority queue

Instead of a

To modify the value of a key:

a. erase the key

b. insert the key with the modified value.

`std::priority_queue<>`

, use a `std::set<>`

with an appropriate predicate.To modify the value of a key:

a. erase the key

b. insert the key with the modified value.

Topic archived. No new replies allowed.