我正在尝试实现 Prim 算法,为此我需要为优先级队列提供 reductionKey 方法(以更新优先级队列中的键值)。我可以在 STL 优先级队列中实现这个吗?
如果有帮助,这就是我正在遵循的算法:
- 对于图 G 中的每个顶点 u
- 将 u 的键设置为 INFINITY
- 将你的父级设置为 NIL
- 将源顶点的键设置为 0
- 排队到优先级队列 Q 图中所有顶点与上面的键
- 而 Q 不为空
- 弹出 Q 中键最低的顶点 u
- 对于你的每个相邻顶点 v
- 如果 (v 还在 Q) 并且 (key(u) + weight-function(u, v) < key(v)) 那么
- 将 u 设置为 v 的父级
- 将 v 的键更新为等于 key(u) + weight-function(u, v) // 这部分给我带来了问题,因为我不知道如何在优先级队列中实现 reduceKey
- 如果 (v 还在 Q) 并且 (key(u) + weight-function(u, v) < key(v)) 那么