基于C#实现Dijkstra算法

或许在生活中,经常会碰到针对某一个问题,在众多的限制条件下,如何去寻找一个最优解?可能大家想到了很多诸如“线性规划”,“动态规划”这些经典策略,当然有的问题我们可以用贪心来寻求整体最优解,在图论中一个典型的贪心法求最优解的例子就莫过于“最短路径”的问题。

一、概序

从下图中我要寻找 V0 到 V3 的最短路径,你会发现通往他们的两点路径有很多:V0->V4->V3,V0->V1->V3,当然你会认为前者是你要找的最短路径,那如果说图的顶点非常多,你还会这么轻易的找到吗?下面我们就要将刚才我们那点贪心的思维系统的整理下。
image.png

二、构建

如果大家已经了解 Prim 算法,那么 Dijkstra 算法只是在它的上面延伸了下,其实也是很简单的。

2.1、边节点

这里有点不一样的地方就是我在边上面定义一个 vertexs 来记录贪心搜索到某一个节点时曾经走过的节点,比如从 V0 贪心搜索到 V3 时,我们 V3 的 vertexs 可能存放着 V0,V4,V3 这些曾今走过的节点,或许最后这三个节点就是我们要寻找的最短路径。

 #region 边的信息
 /// <summary>
 /// 边的信息
 /// </summary>
 public class Edge
 {
     //开始边
     public int startEdge;

     //结束边
     public int endEdge;

     //权重
     public int weight;

     //是否使用
     public bool isUse;

     //累计顶点
     public HashSet<int> vertexs = new HashSet<int>();
 }
 #endregion

2.2、Dijkstra 算法

image.png
首先我们分析下 Dijkstra 算法的步骤:
有集合 M={V0,V1,V2,V3,V4}这样 5 个元素,我们用 TempVertex 表示该顶点是否使用。
Weight 表示该 Path 的权重(默认都为 MaxValue)。
Path 表示该顶点的总权重。
①. 从集合 M 中挑选顶点 V0 为起始点。给 V0 的所有邻接点赋值,要赋值的前提是要赋值的 weight 要小于原始的 weight,并且排除已经访问过的顶点,然后挑选当前最小的 weight 作为下一次贪心搜索的起点,就这样 V0V1 为挑选为最短路径,如图 2。
②. 我们继续从 V1 这个顶点开始给邻接点以同样的方式赋值,最后我们发现 V0V4 为最短路径。也就是图 3。
……
③. 最后所有顶点的最短路径就这样求出来了 。

 #region Dijkstra算法
 /// <summary>
 /// Dijkstra算法
 /// </summary>
 public Dictionary<int, Edge> Dijkstra()
 {
     //收集顶点的相邻边
     Dictionary<int, Edge> dic_edges = new Dictionary<int, Edge>();

     //weight=MaxValue:标识没有边
     for (int i = 0; i < graph.vertexsNum; i++)
     {
         //起始边
         var startEdge = i;

         dic_edges.Add(startEdge, new Edge() { weight = int.MaxValue });
     }

     //取第一个顶点
     var start = 0;

     for (int i = 0; i < graph.vertexsNum; i++)
     {
         //标记该顶点已经使用过
         dic_edges[start].isUse = true;

         for (int j = 1; j < graph.vertexsNum; j++)
         {
             var end = j;

             //取到相邻边的权重
             var weight = graph.edges[start, end];

             //赋较小的权重
             if (weight < dic_edges[end].weight)
             {
                 //与上一个顶点的权值累加
                 var totalweight = dic_edges[start].weight == int.MaxValue ? weight : dic_edges[start].weight + weight;

                 if (totalweight < dic_edges[end].weight)
                 {
                     //将该顶点的相邻边加入到集合中
                     dic_edges[end] = new Edge()
                     {
                         startEdge = start,
                         endEdge = end,
                         weight = totalweight
                     };

                     //将上一个边的节点的vertex累加
                     dic_edges[end].vertexs = new HashSet<int>(dic_edges[start].vertexs);

                     dic_edges[end].vertexs.Add(start);
                     dic_edges[end].vertexs.Add(end);
                 }
             }
         }

         var min = int.MaxValue;

         //下一个进行比较的顶点
         int minkey = 0;

         //取start邻接边中的最小值
         foreach (var key in dic_edges.Keys)
         {
             //取当前 最小的 key(使用过的除外)
             if (min > dic_edges[key].weight && !dic_edges[key].isUse)
             {
                 min = dic_edges[key].weight;
                 minkey = key;
             }
         }

         //从邻接边的顶点再开始找
         start = minkey;
     }

     return dic_edges;
 }
 #endregion

image.png

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/184397.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

vue3.0使用leaflet

1、获取天地图密钥; 访问:https://www.tianditu.gov.cn/ 注册并登录,访问开发资源 =》地图API =》 地图服务=》申请key 应用管理=》创建新应用=》获取到对应天地图key 2、引入leaflet组件 参考资料:https://leafletjs.com/reference.html#path npm install leaflet …

用自己热爱的事赚钱,是多么的幸福

挖掘天赋可能有些困难&#xff0c;但挖掘爱好就简单多啦&#xff01;最幸福的事情就是能用自己喜欢的事情赚钱。 我们要说的是一个博主&#xff0c;他非常喜欢骑自行车&#xff0c;虽然他的工作是在外贸公司做销售&#xff0c;但每当有空时&#xff0c;他都会骑自行车。而且他…

竞赛选题 题目: 基于深度学习的疲劳驾驶检测 深度学习

文章目录 0 前言1 课题背景2 实现目标3 当前市面上疲劳驾驶检测的方法4 相关数据集5 基于头部姿态的驾驶疲劳检测5.1 如何确定疲劳状态5.2 算法步骤5.3 打瞌睡判断 6 基于CNN与SVM的疲劳检测方法6.1 网络结构6.2 疲劳图像分类训练6.3 训练结果 7 最后 0 前言 &#x1f525; 优…

MES管理系统需要与ERP系统协同工作吗

在当前的制造业环境中&#xff0c;信息化、智能化、数字化已经成为了企业转型升级的重要方向。其中&#xff0c;ERP企业管理系统与MES生产管理系统的应用和实施&#xff0c;对于提升企业的运营效率和竞争力具有显著效果。然而&#xff0c;在面对系统工具选择时&#xff0c;许多…

内网横向技术

如果拿下了一台机器之后寻找域控机器 ipconfig /all 找到域名 ping 域名或者nslookup域名

局域网协议:动态主机配置协议(Dynamic Host Configuration Protocol,DHCP)

在局域网络中&#xff0c;DHCP协议通过自动化和简化网络配置过程&#xff0c;提高网络的可管理性和灵活性&#xff0c;使得设备可以更轻松地连接到网络并获得所需的网络配置信息。 文章目录 What is DHCP?DHCP的组成1. DHCP客户端2. DHCP服务器&#xff1a;3. 中继代理&#…

Linux CentOS7的主机名

主机名&#xff0c;也称为计算机名&#xff0c;是提供给网络连接的设备&#xff08;如系统、交换机、路由器等&#xff09;的识别名称。同一网络中不能有两个主机名相同的系统。Linux系统给当前主机命名的目的是能够容易记住&#xff0c;尤其是在部署集群的时候更加方便。 一般…

第二证券:股票破发后面还会涨吗?

许多出资者遇到这样的状况&#xff0c;自己心里也着急及担忧。破发是股价掉破了发行价&#xff0c;这种状况下就会引起出资者的不安。那么股票破发后边还会涨吗&#xff1f;这个问题没有定论&#xff0c;需求从多个视点进行分析和判别。 从经济基础面来看&#xff0c;破发的股…

JSP EL表达式之 empty

好 本文我们还是继续说EL表达式 我们来讲一个非空判断的好手 empty 我们直接编写代码如下 <% page contentType"text/html; charsetUTF-8" pageEncoding"UTF-8" %> <%request.setCharacterEncoding("UTF-8");%> <!DOCTYPE html&…

Maven 简单配置阿里云镜像

配置步骤&#xff1a; 1、找到 maven 的安装目录&#xff0c;修改settings.xml 2、在文件中找到<mirrors>标签&#xff0c;然后再标签中添加阿里云配置即可 <mirror><id>aliyunmaven</id><mirrorOf>*</mirrorOf><name>阿里云公共…

Echarts+Vue+dataV 首页大屏静态示例Demo

效果图: <template><div class="content bg"><!-- 全屏容器 --><!-- 第一行 --><div class="module-box"><div style="flex: 0 1 30%"><dv-decoration-10 style="height: 5px" /></div…

2016年2月17日 Go生态洞察:Go 1.6版本发布

&#x1f337;&#x1f341; 博主猫头虎&#xff08;&#x1f405;&#x1f43e;&#xff09;带您 Go to New World✨&#x1f341; &#x1f984; 博客首页——&#x1f405;&#x1f43e;猫头虎的博客&#x1f390; &#x1f433; 《面试题大全专栏》 &#x1f995; 文章图文…

简述马尔可夫链【通俗易懂】

前言 马尔可夫链&#xff08;Markov Chain&#xff09;可以说是机器学习和人工智能的基石&#xff0c;在强化学习、自然语言处理、金融领域、天气预测、语音识别方面都有着极其广泛的应用。 The future is independent of the past given the present 未来独立于过去&#xff…

批量将本地N个英文Html文档进行中文翻译-操作篇

Unity3D特效百例案例项目实战源码Android-Unity实战问题汇总游戏脚本-辅助自动化Android控件全解手册再战Android系列Scratch编程案例软考全系列Unity3D学习专栏蓝桥系列ChatGPT和AIGC &#x1f449;关于作者 专注于Android/Unity和各种游戏开发技巧&#xff0c;以及各种资源分…

GPT、GPT-2、GPT-3论文精读笔记

视频&#xff1a;GPT&#xff0c;GPT-2&#xff0c;GPT-3 论文精读【论文精读】_哔哩哔哩_bilibili MAE论文&#xff1a;把bert用回计算机视觉领域 CLIP论文&#xff1a;打通文本和图像 GPT 论文&#xff1a;Improving Language Understanding by Generative Pre-Training …

Android开发从0开始(Activity篇)

Activity的生命周期 对应解释&#xff1a; startActivity(new Intent(源页面.this,目标页面.class)) 结束当前活动页面finish(); Activity的启动模式 App先后打开两个活动&#xff0c;此时活动会放入栈内。 &#xff08;Android:launchMode”standard”&#xff09;默认 &am…

全自动洗衣机什么牌子好?内衣洗衣机推荐

现在洗内衣内裤也是一件较麻烦的事情了&#xff0c;在清洗过程中还要用热水杀菌&#xff0c;还要确保洗衣液是否有冲洗干净&#xff0c;还要防止细菌的滋生等等&#xff0c;所以入手一款小型的烘洗全套的内衣洗衣机是非常有必要的&#xff0c;专门的内衣洗衣机可以最大程度减少…

实时语音克隆:5 秒内生成任意文本的语音 | 开源日报 No.84

CorentinJ/Real-Time-Voice-Cloning Stars: 43.3k License: NOASSERTION 这个开源项目是一个实时语音克隆工具&#xff0c;可以在5秒内复制一种声音&#xff0c;并生成任意文本的语音。 该项目的主要功能包括&#xff1a; 从几秒钟的录音中创建声纹模型根据给定文本使用参考…

聚类笔记/sklearn笔记:Affinity Propagation亲和力传播

1 算法原理 1.1 基本思想 将全部数据点都当作潜在的聚类中心(称之为 exemplar )然后数据点两两之间连线构成一个网络( 相似度矩阵 )再通过网络中各条边的消息( responsibility 和 availability )传递计算出各样本的聚类中心。 1.2 主要概念 Examplar聚类中心similarity S(i…

GitHub桌面版

GitHub桌面版 一、GitHub 桌面版二、clone 仓库三、更新仓库 一、GitHub 桌面版 二、clone 仓库 三、更新仓库