当前位置: 动力学知识库 > 问答 > 编程问答 >

c++ - Should I use mutable priority queue for dikjstra/A* algorithm?

问题描述:

I am trying to implement A* algorithm and Dikjstra algorithm as a special case of A* (just pass h(x){return 0;} to A*), when choosing the priority_queue, I have two choices

  1. use an empty priority_queue, and push start point when initializing, and do "pop u, push neighbors of u satisfying certain conditions", in this

    way, one node might be pushed twice if it is a common neighbor of

    two other nodes.

  2. use a mutable priority queue that supports

    update()/decreaseKey()/increaseKey(), I could choose data

    structures in boost::heap or I could (actually I have) implement a

    priority_queue by myself, in this way, all nodes are needed to be pushed to the container when initializing and handles for them need to be kept.

what are the pros and cons of these two strategies and which one is more practical?

网友答案:

A common implementation of a priority queue for Dijkstra's in C++ uses std::set, where the smallest item is set.begin(), and you can find an exact item and erase it. You can also easily define a facade which allows to access std::set with a priority queue-like interface and support the additional update/erase/increaseKey/decreaseKey methods.

Look here for code samples for Dijkstra's implementations with both std::set and std::priority_queue: https://www.topcoder.com/community/data-science/data-science-tutorials/power-up-c-with-the-standard-template-library-part-2/#dijkstra2

This article also makes a claim, that the performance is naturally the same, whether you use std::priority_queue and discard stale items you've popped, or you use std::set and erase the old item immediately.

分享给朋友:
您可能感兴趣的文章:
随机阅读: