我正在尝试实现Prim的算法,为此我需要为优先级队列使用reduceKey方法(以更新优先级队列中的键值).我可以在STL优先级队列中实现吗？
如果它有帮助,这是我遵循的算法:
- 对于图G中的每个顶点u
- 将你的关键设置为INFINITY
- 将u的父级设置为NIL
- 将源顶点的键设置为0
- en-queue to priority queue Q图中的所有顶点,如上所示
- 而Q不是空的
- 在Q中使用最低键弹出顶点u
- 对于你做的每个相邻顶点v
- if(v仍在Q中)和(key(u)+ weight-function(u,v)<key(v))然后
- 设定你是v的父母
- 更新v键等于键(u)+权重函数(u,v) //这部分给我带来问题,因为我不知道如何在优先级队列中实现reduceKey