首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >如果使用最大优先级队列,Dijkstra算法是如何工作的?

问如果使用最大优先级队列,Dijkstra算法是如何工作的?
EN

Stack Overflow用户
提问于 2020-04-26 03:31:52
回答 1查看 306关注 0票数 0

我最近看了一些Dijkstra算法的代码。代码的目标是找到从顶点1到顶点N的最小成本路径。我在查看问题的解决方案时遇到了以下工作代码:

代码语言:javascript
复制
void dijkstra(int start, int n) {
    for(int i = 0; i<n; i++) {
        dist[i] = INF;
        pred[i] = -1;
    }
    dist[start] = 0;  
    priority_queue<ll> q;
    q.push(0);
    int u = 0;
    while(q.size()) {
        u = q.top();
        q.pop();
        for(int end : adj[u]) {
            ll w = weight.at(mp(u, end));
            if(dist[u] + w < dist[end]) {
                dist[end] = dist[u] + w;
                pred[end] = u;
                q.push(end);
            }
        } 
    }
}

该程序使用优先级队列来确定要遍历的下一个顶点(从顶点1开始)。然而,该算法实现的优先级队列是标准的C++优先级队列,它是一个最大优先级队列。这意味着最大的元素具有最高的优先级。然而,我认为在Dijkstra的算法中,我们想要首先轮询最小的顶点?我不确定使用最大优先级队列对此算法是如何工作的。

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2020-04-26 04:21:05

你提到的一切都是对的。但是,要小心!在此算法中,u是邻居的索引。而且,如果具有较高索引的邻居具有较小的距离,则它将正常工作。

此外,您应该注意到,可以使用std::greater实现优先级队列,使顶部元素成为最小的值。

票数 3
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/61431425

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档