首页 > 编程语言 >dijkstra算法详解

dijkstra算法详解

时间:2024-03-19 21:56:48浏览次数:28  
标签:迭代 int 算法 vis dijkstra 详解 dis

今天给大家讲解\(dijkstra\)图论最短路算法

在讲解\(dijkstra\)算法之前,先来给大家讲解一下图论中的松弛操作。

松弛,即\(relaxtion\),是一种编程学术语。

举例说明,例如我们可以从某个机场坐飞机达到若干个机场,然后从这些机场出发,我们又需做火车前往若干个城镇。现在假设我们手里有飞行时间表(\(list\) 或者 \(dict\)),而 \(A_u\) 表示的是从当前位置出发,我们到达 \(u\) 机场所需的时间。类似地,我们用 \(b_{uv}\) 来表示坐火车从 u 机场到达 v 城镇所需的时间(B 自然为 \(list\) \(of\) \(lists\) 或 \(dict\))。下面我们从到达各镇的路径中随机选择一条,它所需的时间为 \(C_v\):

C[v] = float('inf')
for u in A:
    C[v] = min(C[v], A[u]+B[u][v]) //

松弛法(relaxation)是一数学术语,描述的是一些求解方法,这些方法会通过逐步接近的方式获得相关问题的最佳解法。每运用一次松弛法就好像我们“移动”了一次,而我们要做的就是在尽可能少的移动次数内找到最佳解决方案。

理论上来说,我们可以在整个空间上运用相关的松弛法,但关键在于找到一个正确的执行次序。

讲完了松弛法,接下来就给大家讲解\(dijkstra\)算法

(1).\(dijkstra\)算法解决问题范围

\(dijkstra\)算法主要解决的是单源点的最短路和最短路径问题,
且路径的权值不为负权。

(2).\(dijkstra\)算法思想及原理

\(dijkstra\)算法思想是基于贪心算法思想的。所谓贪心算法即始终保持当前迭代解为当前最优解。意思就是在已知的条件下或是当前拥有的全部条件下保证最优解,若在此后的迭代中由于加入了新的条件使得产生了更优解则替代此前的最优解。通过不断的迭代不断保证每次迭代的结果都是当前最优解,那么当迭代到最后一轮时得到的就会是全局最优解。 由于下一轮迭代会参考上一轮的最优解,因此每一轮的迭代的工作量基本一致,降低了整体工作的复杂性。

(3).\(dijkstra\)算法描述

我们假设现在要求出\(k\)点到其他点的距离。

首先将\(k\)点加入一个集合,让他在集合标记为已知,意思就是已经确定\(k\)点到达该点的最短路径,没有标记为已知的点就默认为在未知集合。

然后运用\(k\)进行松弛他的后继节点。

接着找出在未知集合中里找出距离\(k\)最近的点,将它设为新的起点\(k\)。

最后就重复以上流程\(n\)次(\(n\)为顶点数)。

(4).\(dijkstra\)算法具体流程

qwq

(5).\(dijkstra\)算法的优化

我们发现,普通的\(dijkstra\)算法中,“寻找距离\(k\)最近的一个点”这一步我们可以进行优化。我们可以把已知的点和到起点的距离放进一个优先队列里,然后每次取出队头的那个点来当作起点进行下面的操作(队头的点应是到起点距离最小的点,要变动一下排序规则)

(6).\(dijkstra\)算法核心代码

优化前:

void Dijkstra(int k1)
{
    //vis为已知集合,dis表示k1到其他点的最小距离
    memset(dis,0x3f,sizeof(vis));
    vis[k1]=1;
    dis[k1]=0;
    for(int i=1;i<m;++i)
    {
        for(int j=fst[k1];j;j=arr[j].nxt)//链式前向星
        {
           //松弛
            int tmp=arr[j].u;
            if(dis[k1]+arr[j].v<dis[tmp])
            {
                dis[tmp]=dis[k1]+arr[j].v;
                last[tmp]=k1;
            }
        }
        int mid=0x3f3f3f3f;
        //寻找距离起点最小的点
        for(int j=1;j<=m;++j)
        {
            if(vis[j]==0&&dis[j]<mid)
            mid=dis[j],k1=j;
        }
        vis[k1]=1;
    }
}

优化后:

dis[s]=0;
q.push(make_pair(0,s));
while(!q.empty())//排序规则请运用结构体重载自己设定,这里不做阐述
{
    int x=q.top().second;//取出点
    q.pop();
    if(vis[x]==1)//如果这个点已经被压入队列过,不执行这一次循环。
        continue;
    vis[x]=1;
    //松弛
    for(int i=head[x];i;i=e[i].next)
    {
        int y=e[i].to,z=e[i].w;
        if(dis[x]+z<dis[y])
        {
            dis[y]=dis[x]+z;
            q.push(make_pair(-dis[y],y));//将所有距离和点压入队列
        }
    }
}

(7).\(dijkstra\)算法时间复杂度

普通\(dijkstra\):\(O(n^2)\)

优化后的\(dijkstra\):\(O(nlogn)\)

(8).\(dijkstra\)输出路径

dis[s]=0;
q.push(make_pair(0,s));
while(!q.empty())
{
   int x=q.top().second;
   q.pop();
   if(vis[x]==1)
       continue;
   vis[x]=1;
   for(int i=head[x];i;i=e[i].next)
   {
       int y=e[i].to,z=e[i].w;
       if(dis[x]+z<dis[y])
       {
           dis[y]=dis[x]+z;
           last[y]=x;
           q.push(make_pair(-dis[y],y));
       }
   }
}
void print(int t)
{
    if(last[t])
    print(last[t]);
    cout<<t<<" ";
}
    

以上就是\(dijkstra\)算法的全部内容了,希望大家有所收获

参考资料:

unique_pursuit的dijkstra算法详解(迪杰斯特拉算法)简单易懂

Nicola-Zhang的relaxation(松弛法)定义理解

标签:迭代,int,算法,vis,dijkstra,详解,dis
From: https://www.cnblogs.com/SFsaltyfish/p/18084053

相关文章

  • 代码随想录算法训练营day28 | leetcode 93. 复原 IP 地址、78. 子集、90. 子集 II
    目录题目链接:93.复原IP地址-中等题目链接:78.子集-中等题目链接:90.子集II-中等题目链接:93.复原IP地址-中等题目描述:有效IP地址正好由四个整数(每个整数位于0到255之间组成,且不能含有前导0),整数之间用'.'分隔。例如:"0.1.2.201"和"192.168.1.1"是有效IP......
  • 【蓝桥杯选拔赛真题70】python最短路径和 第十五届青少年组蓝桥杯python选拔赛真题 算
    目录python最短路径和一、题目要求1、编程实现2、输入输出二、算法分析三、程序编写四、程序说明五、运行结果六、考点分析七、 推荐资料1、蓝桥杯比赛2、考级资料3、其它资料python最短路径和第十五届蓝桥杯青少年组python比赛选拔赛真题一、题目要求(注:i......
  • 监督学习算法——决策树
    本篇承接上篇文章监督学习算法——线性模型决策树importsyssys.pathmglearn.plots.plot_animal_tree()1.构建决策树我们在下图所示的二位分类数据集上构造决策树。这个数据集由2个半月形组成,每个类别都包含50个数据点。我们将这个数据集称为two_moons。学习决策......
  • raft算法和etcd代码解析-1.raft基本概念
    笔记导言该系列笔记用于GO语言和RAFT算法学习前部分介绍raft算法后部分介绍etcd代码etcd源码来自github,版本主要为ectd-3.1.5本文主要根据视频:<<raft算法工程案例之etcd源码导读>><<解析分布式共识算法之Raft算法>>以上视频作者主页:https://space.bilibili.com/317473362......
  • Go: 泛型及其应用详解
    在软件开发的世界里,泛型是一个强大的工具,它允许我们编写灵活且可重用的代码。对于我们这些追求成为软件架构师和系统架构师的开发者来说,深入理解并有效应用泛型是提升我们代码设计能力的关键一步。Go语言自1.18版本起正式引入了泛型功能,这一变化无疑给Go语言带来了更广阔的......
  • seq2seq项目详解
    一、seq2seq和encoder-decoder关系seq2seq是从解决问题的目的角度来说的,利用的框架是encoder-decoder 二、项目例子比如我们有两个文件letters_source.txt和letters_target.txt,他们行数一致,也就是我们的训练集合,他们每一行互应(这两个文件同一行彼此长度可以不一致:比如中......
  • 高精度算法(大数的加、减、乘、除)
    在C/C++中,int占一个机器字长,32位机中则占4个字节,即[-2^31,2^31-1](10的9次方数量级)。不管是32位还是64位机,longlong占8个字节,即[-2^63,2^63-1](10的18次方数量级)。如果超过该数量级,应该使用高精度算法。1加1、将两个加数逆序存储在两个int数组中。(逆序的原因是方便操作和数......
  • 实现数据结构与算法学习笔记(java)——顺序表顺序栈代码实现
    顺序表实现顺序栈实现......
  • js数组方法详解
    数组是js中最常用到的数据集合,其内置的方法有很多,熟练掌握这些方法,可以有效的提高我们的工作效率,同时对我们的代码质量也是有很大影响。 创建数组一.字面量方式constarray=[1,2,3,4,5]; 二.使用Array构造方法1.无参构造-创建一个长度为0的空数组constarray......
  • c++学习记录 STL—常用查找算法
    一、算法简介find               //查找元素find_if             //按条件查找元素adjacent_find       //查找相邻重复元素binary_search      //二分查找法count        ......