Dijsktra算法理解笔记

这篇具有很好参考价值的文章主要介绍了Dijsktra算法理解笔记。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Dijsktra算法理解笔记

学习了柳神的笔记 感谢柳神

Dijkstra算法是处理图问题中的最短路径的问题
最短路径问题可以大致分为两个方向

  1. 单源最短路径
  2. 全局最短路径

以此为基准可以将最短路径算法这样划分:

  • 单源最短路径
  1. Dijkstra :不能求负权边
  2. Bellman-Ford:可求负
  3. SPFA :可求负。是2的优化
  • 全局最短路径
  1. Floyed:可求负。

其中注意:点到点可以使用深度优先遍历

下面将着重分析Dijsktra算法

伪代码:

Dijkstra() {
  初始化;
  for(循环n次) {
    u = 使dis[u]最小的还未被访问的顶点的编号;
    记u为确定值;
    for(从u出发能到达的所有顶点v){
      if(v未被访问 && 以u为中介点使s到顶点v的最短距离更优)
        优化dis[v];
    }
  }
}

思想:内外循环。外循环起到遍历所有点的作用。内循环1找到还未被访问的离起点最近的点,可以理解为从起点每一步都选择最短路径,目前走到了这个点。内循环2用于找到目前走到的这个点再往下走该选择的最短路径点。

//邻接矩阵
int n, e[maxv][maxv];
int dis[maxv], pre[maxv];// pre用来标注当前结点的前一个结点
bool vis[maxv] = {false};
void Dijkstra(int s) {
  fill(dis, dis + maxv, inf);//初始化距离矩阵
  dis[s] = 0;//起点的距离置为0
  for(int i = 0; i < n; i++) pre[i] = i; //初始状态设每个点的前驱为自身
  
  //进入两层循环
  for(int i = 0; i < n; i++) {
    int u = -1, minn = inf;
    for(int j = 0; j < n; j++) {
      if(visit[j] == false && dis[j] < minn) {
        u = j;
        minn = dis[j];
      }
    }
    if(u == -1) return;
    visit[u] = true;
    for(int v = 0; v < n; v++) {
      if(visit[v] == false && e[u][v] != inf && dis[u] + e[u][v] < dis[v]) {
        dis[v] = dis[u] + e[u][v];
        pre[v] = u; // pre用来标注当前结点的前一个结点
      }
    }
  }
}

该部分为邻接矩阵情况的Dikjkstra算法实现。两个关键数组:dis[maxv]和vis[maxv]。初始起点距离置为0。在两层循环起始,设置u,标记现在访问至哪一点。若没有未访问的点,那么说明已经走完了。接着内循环2,判定u点到其余未访问点的距离,判优更新。
上述代码还加入了标注前一个结点的pre[maxv]数组。

//邻接表
struct node {
  int v, dis;
}
vector<vector<node>> e[maxv];
int n;
int dis[maxv], pre[maxv];// pre用来标注当前结点的前一个结点
bool visit[maxv] = {false};
for(int i = 0; i < n; i++) pre[i] = i; //初始状态设每个点的前驱为自身
void Dijkstra(int s) {
  fill(dis, dis + maxv, inf);
  dis[s] = 0;
  for(int i = 0; i < n; i++) {
    int u = -1, minn = inf;
    for(int j = 0; j < n; j++) {
      if(visit[j] == false && dis[j] < minn) {
        u = j;
        minn = dis[j];
      }
    }
    if(u == -1) return ;
    visit[u] = true;
    //核心区别在于这里!!
    for(int j = 0; j < e[u].size(); j++) {
      int v = e[u][j].v;
      if(visit[v] == false && dis[u] + e[u][j].dis < dis[v]) {
        dis[v] = dis[u] + e[u][j].dis;
        pre[v] = u;
      }
    }
  }
}

该部分为邻接表情况的Dijkstra算法实现。与邻接矩阵大致相同,核心区别在于内循环2的更新是如何提取边权的而已。

输出最短路径,就要用到前面设置的pre数组了。注意要倒序输出

void dfs(int s, int v) {
  if(v == s) {
    printf("%d\n", s);
    return ;
  }
  dfs(s, pre[v]);
  printf("%d\n", v);
}

至此,Dijkstra的基本操作和代码就差不多了。 下面是柳神给的三种附加考法。

  1. 边权+边权
    以一个边权为判断最短路径的标准,另一个边权为多条最短路径时的挑选准则。
for(int v = 0; v < n; v++) { //重写v的for循环
  if(visit[v] == false && e[u][v] != inf) {
    if(dis[u] + e[u][v] < dis[v]) {
      dis[v] = dis[u] + e[u][v];
      c[v] = c[u] + cost[u][v];
    }else if(dis[u] + e[u][v] == dis[v] && c[u] + cost[u][v] < c[v]) {
      c[v] = c[u] + cost[u][v];
    }
  }
}

这里主要判断最短路径的边权为e[maxv][maxv],第二个边权为cost[maxv][maxv]。

  1. 边权+点权
    以一个边权为判断最短路径的标准,另一个点权为多条最短路径时的挑选准则
for(int v = 0; v < n; v++) {
  if(visit[v] == false && e[u][v] != inf) {
    if(dis[u] + e[u][v] < dis[v]) {
      dis[v] = dis[u] + e[u][v];
      w[v] = w[u] + weight[v];
    }else if(dis[u] + e[u][v] == dis[v] && w[u] + weight[v] > w[v]) {
      w[v] = w[u] + weight[v];
    }
  }
}

这里主要判断最短路径的边权为e[maxv][maxv],第二个边权为weight[maxv]。

1和2的核心都在于要更新c[maxv]和w[maxv],尤其要在边权未改变时判断第二个指标(边权或者点权)。

  1. 问有多少条最短路径
    核心在于增加一个num [ ]。起点的值置为1。其余置为0。在循环的过程中,遇到相等情况,将前一个点的路径数加到后一个点上。最后输出想要终点的值。
for(int v = 0; v < n; v++) {
  if(visit[v] == false && e[u][v] != inf) {
    if(dis[u] + e[u][v] < dis[v]) {
      dis[v] = dis[u] + e[u][v];
      num[v] = num[u];
    }else if(dis[u] + e[u][v] == dis[v]) {
      num[v] = num[v] + num[u];
    }
  }
}

柳神博文中还介绍了一个例子,非常值得学习!再次感谢柳神文章来源地址https://www.toymoban.com/news/detail-790185.html

到了这里,关于Dijsktra算法理解笔记的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 《深入理解Java虚拟机》读书笔记:HotSpot的算法实现

    HotSpot的算法实现概要 由于目前的主流Java虚拟机使用的都是准确式GC(这个概念在第1章介绍Exact VM对Classic VM的改进时讲过),所以当执行系统停顿下来后,并不需要一个不漏地检查完所有执行上下文和全局的引用位置,虚拟机应当是有办法直接得知哪些地方存放着对象引用。

    2024年02月13日
    浏览(62)
  • 算法~base64算法理解

    Base64 是一种用于将二进制数据编码成 ASCII 字符的编码方式。它主要用于在文字环境中传输或存储二进制数据,如在电子邮件、XML 文件、URL 参数等。Base64 编码不是一种加密算法,而是一种编码方式,其主要作用是将二进制数据转换为文本数据,以便更容易在文本协议中处理

    2024年02月05日
    浏览(45)
  • 【排序算法】-- 深入理解桶排序算法

            在计算机科学中,排序算法是一种对数据进行有序排列的重要技术。桶排序(Bucket Sort)是一种常见的排序算法,它通过将数据分到有限数量的桶中,并对每个桶中的数据分别排序,最后按照顺序将所有桶中的数据合并起来,从而实现整体有序。桶排序的时间复杂度

    2024年03月27日
    浏览(43)
  • 【算法小课堂】深入理解前缀和算法

    前缀和是指某序列的前n项和,可以把它理解为数学上的数列的前n项和,而差分可以看成前缀和的逆运算。合理的使用前缀和与差分,可以将某些复杂的问题简单化。 我们通过一个例子来理解前缀和算法的优势: www.nowcoder.com 我们可以通过暴力的解法去解决这个问题,但是这

    2024年02月08日
    浏览(39)
  • 算法初学者指南:理解排序算法

            排序是计算机科学中的基本问题之一,也是数据处理的核心步骤。从最简单的个人项目到复杂的工业级应用,排序都扮演着关键角色。本文将介绍四种常见的排序算法:冒泡排序、插入排序、快速排序和堆排序,旨在帮助算法初学者理解这些基本概念。         冒泡

    2024年01月23日
    浏览(59)
  • 趣味算法:滑动窗口算法的理解与应用

    在编程和数据结构中,滑动窗口算法是一种常见的解决问题的方法。它主要用于处理涉及连续或固定长度子数组、子序列或子字符串的问题。本文将深入探讨滑动窗口算法,包括其基本概念、应用场景、基本步骤以及具体的Java代码实践。 滑动窗口算法是一种优化技巧,主要

    2024年02月11日
    浏览(36)
  • 趣味算法:搜索算法的理解、应用与优化策略

    一、引言 搜索,这是一种无处不在的行为。当你在社交媒体上寻找老朋友,当你在互联网上浏览信息,当你在电子商务网站上寻找特定的产品,你都在进行搜索。搜索也是计算机科学中的一项基本任务。计算机程序员使用搜索算法从大量数据中找到所需的信息,或者解决复杂

    2024年02月12日
    浏览(36)
  • 【排序算法】深入理解快速排序算法:从原理到实现

    目录 1. 引言 2. 快速排序算法原理 3. 快速排序的时间复杂度分析 4. 快速排序的应用场景 5. 快速排序的优缺点分析 5.1 优点: 5.2 缺点: 6. Java、JavaScript 和 Python 实现快速排序算法 6.1 Java 实现: 6.2 JavaScript 实现: 6.3 Python 7. 总结        快速排序是一种经典的排序算法,它的

    2024年03月20日
    浏览(46)
  • 校验算法--md5算法理解(c语言)

    ​​​​​​​​​​​​​​RFC 1321:MD5 消息摘要算法 (rfc-editor.org) https://www.rfc-editor.org/rfc/rfc1321 官方参考文档,可以直接拷贝References里的代码,MD类型定义为5后直接使用里面的代码是可以成功执行的,MDString这个函数改一下其实就能用,下面是对MD5算法的执行过程进行理解

    2024年02月05日
    浏览(43)
  • 深度理解排序算法——快速排序

    在如今所知的众多排序算法中,快速排序无疑是脱颖而出的一种高效排序算法,在众多的情景下快速排序的算法效率都是数一数二的。闲话少叙,直接开始讲解快速排序的本质。 霍尔版本作为快速排序的最初版本,其他的版本都在霍尔版本的基础上衍生出来,因此掌握好霍尔

    2024年02月03日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包