m0_61221162 2021-08-27 21:56 采纳率: 100%
浏览 123
已结题

Dijkstra算法及邻接表 C++

priority_queue<pair<int,int>>q;//大根堆-小根堆
    memset(d,0x3f,sizeof(d);
    memset(v,0,sizeof(v));
    d[1]=0;
    q.push(make_pair(0,1));
    while(q.size())
    int x=q.top().second;q.pop();
    if(v[x])continue;
    v[x]=1;
    for(int i=head[x];i;i=Next[i])
    int y=ver[i],z=edge[i];
    if(d[y]>d[x]+z){
        d[y]=d[x]+z;
        q.push(make_pair(-d[y],y));
    }
    } 

如上,请问一下:

while(q.size())
if(v[x])continue;
for(int i=head[x];i;i=Next[i])

各是什么意思?还有邻接表的原理是什么?麻烦了!

  • 写回答

1条回答 默认 最新

  • ThXe 2021-08-28 10:13
    关注

    邻接表你可以理解为多个链表,每个链表的头是一个节点,而你添加一条边add(a,b,c)相当于给a增添一个出度b长度为c,而 next[a]中储存的是就是a所有的出度的地址,next存储的是下一个出度的地址,ver[i]就是出度点的标号,edge[i]头节点到出度的距离,dj的基本思路是每次选取一个离原点最近的边来更新其他点的距离,我们先将{0,1}加入堆中,堆排序pair根据first优先原则,所以意思就是堆中1号点到一号点的距离为0,那么此时会用1号点先更新它出度,并且每个点有且只会被加入一次,我们将它打上标记,如果堆中已经加入过这个最短边,我们直接将它continue,否则而循环的终点就是没有边再被更新的时候,也就是没有东西可以入队了,循环结束。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 5月16日
  • 已采纳回答 5月8日
  • 创建了问题 8月27日

悬赏问题

  • ¥15 目标检测算法移植到arm开发板
  • ¥15 利用JD51设计温度报警系统
  • ¥15 快手联盟怎么快速的跑出建立模型
  • ¥15 关于腾讯云服务器中,PHP页面无法打开的问题
  • ¥60 如何把照片修复成原始拍摄图
  • ¥80 Exited too quickly (process log may have details)
  • ¥15 爬知乎登录之后内容加载不出来
  • ¥15 怎么用protues测量通频带
  • ¥15 zepelin使用sparkInterpreter 异常
  • ¥15 paho mqtt 接收不到消息