首页 > 其他分享 >最短路之 $dijekstra$ 学习笔记

最短路之 $dijekstra$ 学习笔记

时间:2024-09-14 17:48:28浏览次数:7  
标签:int 短路 笔记 ww edges dijekstra bian nodes dis

最短路之 \(dijekstra\) 学习笔记

复习 \(dijekstra!\)

怎么说,就写一下 \(dij\) 的实现过程吧

\(dij\) 的思路就是,

将结点分成两个集合:已确定最短路长度的点集(记为$ S$集合)的和未确定最短路长度的点集(记为 $ T$ 集合)。一开始所有的点都属于 $ T $ 集合。

初始化 $dis(s)= 0 $ ,其他点的 $dis $ 均为 $+ \infty $。

然后重复这些操作:

  1. 从$ T $ 集合中,选取一个最短路长度最小的结点,移到 $ S $ 集合中。
  2. 对那些刚刚被加入 $S $ 集合的结点的所有出边指向的点更新距离并放入队列。

直到 $T $ 集合为空,算法结束。

把图上的点分成两个集合,一个是已经确定最短路的集合 \(S\) 和剩下的点 \(S'\)

同时用一个优先队列 \(Q\) 来维护与 \(S\) 中的点相邻的点中到起点 \(s\) 的目前的最短距离(这个地方用 \(pair\) 来同时存距离和点的编号)

然后实现步骤就是

每次取出 \(Q\) 的队头也就是目前不在 \(S\) 之中到起点 \(s\) 距离最近的点 \(i\)

如果这个点之前没被取出来过,也就是没被标记过,不在 \(S\) 之中

则将其标记,也就是放到 \(S\) 中 然后依次遍历 \(i\) 点的所有相邻的节点 \(t\)

如果 \(t\) 不在 \(S\) 之中 且 \(dis(s,i)+dis(i,t)<dis(s,t)\) 的话,就将 \(t\) 放到 \(Q\) 中

当 \(Q\) 重新变为空时,最短路就求好了

时间复杂度

\(O(m\log n+nk\log n) \approx O(m\log n)\)

其中k为每个点的平均邻居数

代码如下

#include <bits/stdc++.h>
using namespace std;
int n, m, k;

struct edge
{
    int f, t;
    int w;
};
edge edges[1000000];
struct node
{
    bool done;
    int dis = 1099999999;
    vector<int> to;
    int num;
    void clear()
    {
        this->done = 0;
        this->dis = 2147483647;
    }
};

node nodes[300000];
//第一关键字是距离,第二关键字是节点编号
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;

void dij(int start_)
{
    int the_bian, the_dis, temp_dis, to_;
    q.push({0, start_});
    nodes[start_].dis = 0;
    while (!q.empty())
    {
        pair<int, int> the_node = q.top();
        q.pop();
        the_dis = the_node.first;
        the_bian = the_node.second;
        if (!nodes[the_bian].done)
        {
            nodes[the_bian].done = 1;//标记,放入S中
            for (int yy = 0; yy < nodes[the_bian].to.size(); yy++)//便利这个点的所有出边
            {
                to_ = edges[nodes[the_bian].to[yy]].t;

                temp_dis = nodes[the_bian].dis + edges[nodes[the_bian].to[yy]].w;
                if (temp_dis < nodes[to_].dis)
                {
                    nodes[to_].dis=temp_dis;//更改距离
                    q.push({temp_dis, to_});//入队
                }
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m >> k;
    int aa, bb, cc;
    for (int ww = 1; ww <= m; ww++)
    {
        cin >> aa >> bb >> cc;//建边
        edges[ww].f = aa;
        edges[ww].t = bb;
        edges[ww].w = cc;
        // edges[ww + m].f = bb;
        // edges[ww + m].t = aa;
        // edges[ww + m].w = cc;
        nodes[aa].to.push_back(ww);
       // nodes[bb].to.push_back(ww + m);
    }
    dij(k);
    for (int yy = 1; yy <= n; yy++)
    {
        cout << nodes[yy].dis << " ";
    }

    return 0;
}

标签:int,短路,笔记,ww,edges,dijekstra,bian,nodes,dis
From: https://www.cnblogs.com/sea-and-sky/p/18414446

相关文章

  • 最小生成树之 Prim 算法学习笔记
    最小生成树之Prim算法学习笔记emm...在一通瞎搞奋战之后,prim被我收入囊中!\(prim\)的思路其实非常简单,和\(dij\)有一丝相似之处,可能会搞混设最小生成树上的集合为\(S\),所有点一开始到\(S\)的距离都是\(+\infty\)从任意一个点开始,将其放入\(S\),然后更新与这个点相邻......
  • self-play RL学习笔记
    让AI用随机的路径尝试新的任务,如果效果超预期,那就更新神经网络的权重,使得AI记住多使用这个成功的事件,再开始下一次的尝试。——llyaSutskever这两天炸裂朋友圈的OpenAI草莓大模型o1和此前代码能力大幅升级的Claude3.5,业内都猜测经过了自博弈强化学习(self-playRL)。1......
  • 3ds Max 2018 进阶快捷键操作笔记
    1.视图与界面控制Alt+W:切换当前视口最大化。工作时常需要在多个视口之间切换,该快捷键帮助快速专注于某一视口细节。F3:切换线框模式与实体模式。方便随时观察模型的结构和表面,特别是在检查复杂几何形状时非常有用。F4:显示网格边缘。在实体模式下显示线框,常用于优化模型的......
  • PMP模拟考试第94题笔记
    注:obstacle障碍commence 开始priorities 优先事项existingrequirements 现有要求barrier 障碍lackof缺乏在敏捷项目中,障碍(obstacle)指的是阻碍团队按计划推进工作的任何因素。障碍通常会影响团队的生产力和工作进度,因此需要被识别和解决。让我们逐一分......
  • 线性代数 3B1B 笔记
    https://www.bilibili.com/video/BV1ys411472E概念秩Rank基础变换后的空间维数线性相关一组向量至少有一个是多余的,没有对张成空间做出任何贡献Atleastoneofthesevectorsisredundant,notaddinganythingtoourspan.解释你有多个向量,并且可以移除其中一个,而不减......
  • 【LeetCode 算法笔记】49. 字母异位词分组
    目录问题描述计数法:计数法(用哈希表):排序法:问题描述给你一个字符串数组,请你将字母异位词组合在一起。可以按任意顺序返回结果列表。字母异位词是由重新排列源单词的所有字母得到的一个新单词。示例1:输入:strs=[“eat”,“tea”,“tan”,“ate”,“nat”......
  • C#笔记13 线程同步概念及其实现,详解lock,Monitor,Mutex代码用法
    同步的概念在我们学会在C#中使用线程之后,我们拥有了把一个程序中的不同代码段在不同线程中运行的能力,可以说此时我们已经能够做到让他们分别执行,异步执行。对于我们的桌面端程序,使用多线程可以让我们在后台进行操作的时候保持用户界面的响应。对于服务器应用程序,多线程可以......
  • Java 21的Logging的笔记
    JavaCoreLibrariesJavaLoggingJDK自带的日志记录框架,提供了基本功能,但在项目中没有实际使用过。通常会使用SLF4J和Log4j2或者Logback搭配。以maven管理的项目为例,修改pom.xml,增加如下配置:<dependency><groupId>org.slf4j</groupId><artifactId>slf4j-api</art......
  • Java 21的Collections Framework的笔记
    JavaCoreLibrariesJavaCollectionsFrameworkCreatingUnmodifiableLists,Sets,andMaps相对于普通的容器类,不可变容器的对象,占用的内存少,内存利用更高效。在仅有只读操作时,使用不可变容器的对象,会有性能和空间方面的优势。不可变List的构建样例代码,如下:List<St......
  • RH436 学习笔记(四)
    集群资源管理constraint这样可以清空票数:下面这条命令可以看到每一个资源缺省的票数:这些规则是永久生效的,需要手动删除;如果是通过move或ban等命令产生的constraint规则,则临时生效,集群重启就失效了。TroubleShootinglog这个日志文件可以配置每个节点不一样;改完配置文件以后重启......