盐城网站开发市场,建筑工程招投标网,微信个人号管理系统,招c1驾驶员300元一天#x1f4af; 博客内容#xff1a;【茶话数据结构】查找最短路径——Dijkstra算法详解 #x1f600; 作 者#xff1a;陈大大陈 #x1f989;所属专栏#xff1a;数据结构笔记 #x1f680; 个人简介#xff1a;一个正在努力学技术的准前端#xff0c;专注基础和实… 博客内容【茶话数据结构】查找最短路径——Dijkstra算法详解 作 者陈大大陈 所属专栏数据结构笔记 个人简介一个正在努力学技术的准前端专注基础和实战分享 欢迎私信 欢迎大家这里是CSDN我总结知识和写笔记的地方喜欢的话请三连有问题请私信 目录
题记
两大注意事项
实例题目
超超超详细图解 答案以及详尽总结
后记
题记 复习到离散数学图论时想起来这个算法感觉很有写博客的必要今天这篇博客就来讲一下查找最短路径的Dijkstra算法。
Dijkstra 算法是由荷兰计算机科学家 Edsger Wybe Dijkstra 在1956年发现的算法戴克斯特拉算法使用类似广度优先搜索的方法解决赋权图的单源最短路径问题。Dijkstra 算法原始版本仅适用于找到两个顶点之间的最短路径后来更常见的变体固定了一个顶点作为源结点然后找到该顶点到图中所有其它结点的最短路径产生一个最短路径树。本算法每次取出未访问结点中距离最小的用该结点更新其他结点的距离。需要注意的是绝大多数的Dijkstra 算法不能有效处理带有负权边的图。
两大注意事项
需要注意两个问题
1.每次从未标记的节点中选择距离出发点最近的节点标记它,收录到最短路径集合中。
2.计算刚加入的节点A的临近节点B的距离不包含标记的节点若节点A的距离节点B的距离到节点B的边长节点B就更新节点B的距离和其前一个位置的点。
实例题目 如图计算从起点0到终点4的最短路径长度。 超超超详细图解 我们作出这样的表格用于施展Dijkstra算法。
出发点表示从出发点到现在位置地距离。
首先从距离出发点最近的点也就是出发点开始它距离出发点的位置显然是0,。
标记它并收录到最优路径集合中我们用一个对钩来表示已被收录。 下一步就是找它的临近节点分别是1和7。
更新1和7的出发点距离和前面点如图。 紧接着从没有被标记的节点中选出出发点距离最短的即为1标记它并收录到最短路径集合中。 紧接着计算它的邻接节点即为7和2因为0已经被标记所以不算。
计算出0和它们的距离分别是15和1212小于默认的正无穷更新。
15比8大不更新。 选出出发点距离最小的点即为7标记它并收录到最短路径集合中。 紧接着计算它的邻接节点即为6和8因为1和0已经被标记所以不算。
计算出0和它们的距离分别是9和15小于默认的正无穷更新。 选出出发点距离最小的点即为6标记它并收录到最短路径集合中。 紧接着计算它的邻接节点即为5和8因为7已经被标记所以不算。
计算出0和它们的距离分别是11和1511的更新15的和之前相等不更新。 选出出发点距离最小的点即为5标记它并收录到最短路径集合中。 紧接着计算它的邻接节点即为2,3和4因为6已经被标记所以不算。
计算出0和它们的距离分别是15和25和21。
15大于12不更新25小于正无穷更新21小于正无穷更新。 选出出发点距离最小的点即为2标记它并收录到最短路径集合中。 紧接着计算它的邻接节点即为3和8因为1和5已经被标记所以不算。
计算出0和它们的距离分别是19和14分别小于25和15都更新。 选出出发点距离最小的点即为8标记它并收录到最短路径集合中。 紧接着计算它的邻接节点全都标记过了最方便的一集小时候写哭了。
直接标记后跳过。 选出出发点距离最小的点即为8标记它并收录到最短路径集合中。 紧接着计算它的邻接节点,就剩下一个4没被标记了。
计算出距离它的距离是28大于21不更新。
最后一步将4标记并收录到最短路径集合中。、
我们的最终答案堂堂出炉 答案以及详尽总结
从上面的表中可以得到答案0到4的最短路径是21。
从头到尾经过的节点是 0 7 6 5 4。
其实需要注意的就这两点。 1.每次从未标记的节点中选择距离出发点最近的节点标记它,收录到最短路径集合中。
2.计算刚加入的节点A的临近节点B的距离不包含标记的节点若节点A的距离节点B的距离到节点B的边长节点B就更新节点B的距离和其前一个位置的点。
后记
韩信带净化成为大牛道阻且长小僧还在山腰上。。。 博客里如果有问题的话还请大佬私信我我会修改的。
有问题的话请私信问我我看到就会回的。
