做网站预算表,wordpress加载插件下载,免费域名分发系统,网页回合制游戏排行榜迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的#xff0c;因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法#xff0c;解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始#xff0c;采用贪心算法的策略…
迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始采用贪心算法的策略每次遍历到始点距离最近且未访问过的顶点的邻接节点直到扩展到终点为止。
关于Dijkstra算法是如何工作的下面我们通过一道例题来说明 首先以T到所有网络节点的最短路径为例
为了方便计算避免后期因为人为的疏忽漏算或者算错我们先把所有的其他点都列出来像这样 其中N是指它开始的地方 首先t与自己肯定为0后选择一个与T连接最短的u下一步TU与x未直接相连距离为infinity同理得出w也为无穷 与y直接相连距离为7.....以此类推它的规范写法如下
以此类推如果你面前有好几条路要走你一定要选择最短的那一条这也是贪心算法的由来
再举个例子
以tuvw为例到x的最短距离为34到v的距离最短为4到y的距离最短为7规范表达如下 注意了数字后面的字母表示的是与目标直接相连再N范围之内的节点这里容易混淆。
总结一下
本文并没有着重与分析dijkstra算法的原理而是采用一道经典的例题来剖析适合于数学基础较低的同学其中所涉及的图论等数学知识感兴趣的读者可以自行去了解。
如有问题欢迎私信或发邮件联系我flightgycqq.com
