首页 > 编程语言 >算法——最短路径算法(dijkstra)

算法——最短路径算法(dijkstra)

时间:2023-06-11 11:33:59浏览次数:59  
标签:dist int dijkstra 最短 source 算法 节点

source 源端, target目的端
1.构造n*n的相邻矩阵, -1表示未相邻
int matrix[n][n]

int  dist[n]  初始化各节点直接到source的距离, dist[source] = 0;
bool visited[n]  是否访问过

    dist[source] = 0;
    for(int i = 0;i<n-1;i++) {
    //找剩余n-1个节点的距离
        int min = INT32_MAX;
        int midx = 0;
        for(int j = 0;j<n;j++){
        //对每个节点判断是否已访问,并找到未访问的距离最短的点
            if (!visited[j] && dist[j] < min){
                min = dist[j];
                midx = j;
            }
        }
        visited[midx] = true;
        dist[midx] = min;
      //对未被访问的节点,通过midx节点为桥梁,更新dist数组
        for (int j = 0; j < n; ++j) {
            if (!visited[j] && matrix[midx][j] > 0){
                dist[j] = min(dist[j], dist[midx] + matrix[midx][j]);
            }
        }
      //不断访问节点,直到所有节点都访问过后,退出循环。
    }

标签:dist,int,dijkstra,最短,source,算法,节点
From: https://www.cnblogs.com/sanguoasd/p/17472721.html

相关文章

  • 【三维装箱】基于自适应遗传算法的三维集装箱装载问题研究附matlab代码
    ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,matlab项目合作可私信。......
  • 一致性哈希算法——算法解决的核心问题是当slot数发生变化时,能够尽量少的移动数据
    一致性哈希算法摘自:http://blog.codinglabs.org/articles/consistent-hashing.html算法简述一致性哈希算法(ConsistentHashing)最早在论文《ConsistentHashingandRandomTrees:DistributedCachingProtocolsforRelievingHotSpotsontheWorldWideWeb》中被提出。简单来......
  • APS规则引擎算法
    要实现APS规则引擎算法,你可以使用C#中的规则引擎库,例如NRules或Drools.NET。以下是一个使用NRules库实现APS规则引擎算法的简单示例:首先,安装NRules库。你可以使用NuGet包管理器控制台运行以下命令来安装NRules:Install-PackageNRules创建规则类和模型类:publicclass......
  • APS排产算法
    APS(AdvancedPlanningandScheduling,高级计划和调度)是一种用于制造业的排产算法,旨在优化生产计划和资源分配,以提高生产效率和交货准时率。APS算法基于现有订单、生产能力、物料需求和约束条件等信息,进行动态规划和优化,以生成最优的生产计划。APS算法通常包括以下几个关键步骤:......
  • 推导&实现:感知器准则&MSE算法&Fisher准则
    推导&实现:感知器准则&MSE算法&Fisher准则1感知器准则1.1推导​ 第二个类别的样本特征向量\(\times-1\),再给所有样本增加一维表示label,第一类label等于\(1\),第二类label等于\(-1\)​ 感知器算法采用最直观的准则,即最小错分样本数,(MSE的区别在于迭代更新\(a\)......
  • 《数据结构与算法》之队列与链表复习
    导言:我们在上一次学习了堆栈的数据结构以后,可以了解到它是受限制的操作,比如我们操作只能在栈顶,现在我们要学习的东西叫做队列,它也是受限制的一种数据结构,它的特点是队头只出数据,而队尾只入数据,它的结构就和它的名字,像我们平时排队一样先来的人肯定要先服务啊,所以它的英文叫做Fri......
  • 【图像去噪】基于图像加噪去噪算法合集附matlab代码
    ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,matlab项目合作可私信。......
  • 文心一言 VS 讯飞星火 VS chatgpt (37)-- 算法导论5.4 1题
    一、一个屋子里必须要有多少人,才能让某人和你生日相同的概率至少为1/2?必须要有多少人,才能让至少两个人生日为7月4日的概率大于1/2?文心一言:一个屋子里必须要有多少人,才能让某人和你生日相同的概率至少为1/2?答案:23人。证明:假设有n个人,生日都在一年365天当中,则某人和你的生日相......
  • 13.双向链表的算法实现
      单链表中每个结点除了存储自身数据之后,还存储了下一个结点的地址,因此可以轻松访问下一个结点,以及后面的后继结点,但是如果想访问前面的结点就不行了,再也回不去了。  例如删除结点p时,要先找到它的前一个结点q,然后才能删掉p结点,单向链表只能往后走,不能向前走。如果需要向前走......
  • 文心一言 VS 讯飞星火 VS chatgpt (37)-- 算法导论5.4 1题
    一、一个屋子里必须要有多少人,才能让某人和你生日相同的概率至少为1/2?必须要有多少人,才能让至少两个人生日为7月4日的概率大于1/2?文心一言:一个屋子里必须要有多少人,才能让某人和你生日相同的概率至少为1/2?答案:23人。证明:假设有n个人,生日都在一年365天当中,则某人和你的......