首页 > 其他分享 >最短路

最短路

时间:2023-09-07 19:44:07浏览次数:31  
标签:int 短路 JCY 更新 num push

dijkstra (好像有问题)

单源最短路,原理比较简单,就是贪心。每次选取最近的边(没选过),用它去更新其他的。传统做法是每次扫一遍寻找最近的遍,其实可以用堆优化。

void dijkstra(int s) {
  q.push(JCY{s, 0});
  for (int i = 1; i <= n + n; i++) {
    num[i] = 0x3f3f3f3f; //有因为最短路
  }
  num[s] = 0;//自己到自己是0
  while (q.size()) {
    JCY p = q.top();
    q.pop();
    if (vis[p.id]) { //选过了
      continue; // 不要
    }
    vis[p.id] = 1; // 标为选过
    for (int j = h[p.id]; j; j = ne[j]) {
      int v = e[j];
      if (num[v] > num[p.id] + w[j]) { //如果能更新
        num[v] = num[p.id] + w[j];
        q.push(JCY{v, num[v]}); //可以对其他人有贡献
      }
    }
  }
}

因为每个点都会进队列 \(O(n)\),然后每次更新 \(O(m)\),堆 \(O(log)\),总共 \(O((n + m)log n)\)

spfa

类似于广搜,选择一个点,然后进行更新

void spfa() {
  for (int i = 1; i <= n; i++) {
    num[i] = 0x3f3f3f3f; //不说
  }
  num[s] = 0;
  vis[s] = 1; //是否在队列里
  q.push(s);
  while (q.size()) {
    int u = q.front(), v;
    q.pop();
    vis[u] = 0;
    for (int i = h[u]; i; i = ne[i]) {
      v = e[i];
      if (num[v] > num[u] + w[i]) { //松弛
        num[v] = num[u] + w[i];
        if (!vis[v]) { //不在队列
          q.push(v);//进队
          vis[v] = 1;
        }
      }
    }
  }
}

还一个晚点写(鸽了好久,不想管了呢)

标签:int,短路,JCY,更新,num,push
From: https://www.cnblogs.com/jiangyuchen12/p/17685913.html

相关文章

  • 最短路
    基本算法:\(dijkstra\)使用条件:无负权边每次取出还未取出过的\(dis\)最小的节点更新其他节点正确性证明:因为是\(dis\)最小的节点,别的节点不可能有一条路径走到这个节点且\(dis\)更小(路径为正)stl-pq默认是大根堆,用负号处理为小根堆intn,m,s,tot;inthead[N],ver[M......
  • LED摩托车灯降压恒流IC内置mos管AP5192短路保护
    AP5192是一款PWM工作模式,高效率、外围简单、内置功率MOS管,适用于4.5-100V输入的高精度降压LED恒流驱动芯片。最大电流1.5A。AP5192可实现线性调光和PWM调光,线性调光脚有效电压范围0.55-2.6V.AP5192工作频率可以通过RT外部电阻编程来设定,同时内置抖频电路,可以降低对其他设备的E......
  • 赋值运算符,自增自减运算符,关系运算符,短路逻辑运算符,三元运算符
           ......
  • 最短路三种算法详解
    最短路最短路问题即,给你一张图,让你求出图中两点的最短距离。这篇文章会讲解\(Dijkstra\)、\(Spfa\)、\(Floyd\)三种算法,让您透彻理解最短路!Dijkstra朴素版题目:\(Dijkstra\)通常是用来解决图中一个定点到其余点的最短距离,基本思路是:从中心向外扩展,直到扩展到终点为止。......
  • 最短路练习
    T1SightseeingCowsG我们先考虑如何求平均乐趣值。1.总乐趣为\(\sum^n_{i=1}f_i\timess_i\),其中\(f_i\)为第\(i\)个点的乐趣值,\(s_i\)表示选不选。2.路径是个环,总长度为\(\sum^n_{i=1}e_i\timess_i\)其中\(e_i\)为从点\(i\)出发所走的边。所以最大平均......
  • 最短路
    简介最短路顾名思义就是求两个点之间的最短距离,在一些题中是非常重要的工具,一般根据不同的情况和限制需使用合适的算法(比如如果有负边权就不能用\(dijkstra\)),一般分为单元最短路和多源最短路。最经典的算法有\(dijkstra\),\(floyd\),\(bellman-ford\)等。在学习最短路之前,必须......
  • 用 Dijkstra 算法解决最短路问题
    话不多说,先看图1.1朴素版的Dijkstra算法一般用到这个情况稠密图,也就是节点的个数比边的个数少。(稠密图用邻接矩阵存储)#include<cstring>#include<iostream>#include<algorithm>usingnamespacestd;constintN=510;intn,m;intg[N][N];//稠密图用邻接矩阵,g......
  • 为什么会变成这样呢? #5(常数边权最短路)
    给定一个\(n\)个点\(m\)条边的有边权无向图,其中边权\(w_i\in\{0,1,\dots,k-1\}\),求点\(1\)到各个点的最短路。期望复杂度:\(O((n+m)k)\)0k最短路在经典的Dijkstra算法中,我们使用一个优先队列来维护松弛队列,这样的时间复杂度为\(O((n+m)\logk)\)。现在我们考虑为每种......
  • 最短路总结
    最短路径目录最短路径\(\operatorname{Floyd}\)(全源最短路)\(\operatorname{Dijkstra}\)(非负权图单源最短路)\(\operatorname{Bellman-Ford}\)(带负权单源最短路)\(\operatorname{Johnson}\)(全源最短路)总结参考文献:\(\operatorname{Floyd}\)(全源最短路)我们定义一个数组\(f_{k,x,y......
  • 单源最短路问题
    Bellman-Ford算法例题【模板】负环原理Bellman-Ford算法的原理是重复遍历\(n-1\)遍所有的边,对其进行松弛操作。如果源点到终点的距离小于源点到起点与这条边的权值之和,那么源点到终点的距离就用这个更小的距离来替换。核心代码:if(dis[e[j].from]+e[j].value<......