使用priority_queue实现dijskstra

使用priority_queue可以很方便地实现Dijkstra算法。首先，我们可以将用于存储节点距离的数组dis[i取相反数，以便将priority_queue默认为大根堆（从小到大排序）。然后，我们可以使用优先队列priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>来存储节点和对应的距离值，其中pair的第一个元素表示距离值，第二个元素表示节点。在每次迭代中，我们可以从优先队列中取出距离值最小的节点，并更新其相邻节点的距离值。这样可以保证每次取出的节点都是当前最短路径的节点，直到所有节点都被访问完毕。使用优先队列的插入和删除操作的时间复杂度为O(log2n)，所以整个Dijkstra算法的时间复杂度为O(Elog2n)，其中E是边的数量，n是节点的数量。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* *3* [堆优化的dijkstra算法](https://blog.csdn.net/qq_42636949/article/details/119155734)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT0_1"}}] [.reference_item style="max-width: 100%"]
[ .reference_list ]