首页 > 编程语言 >【科研相关知识】Dijkstra算法

【科研相关知识】Dijkstra算法

时间:2024-04-10 22:33:22浏览次数:26  
标签:科研 -- 路径 算法 距离 最短 访问 Dijkstra 节点

Dijkstra算法

相关背景知识

  • Dijkstra算法是解决图论中的最短路径问题
  • 而最短路径问题是在图中找到两个节点之间的最短路径
  • 在导航中确定路线最短,在网络中路由器使用Dijkstra算法确定最短路径和转发端口。
  • 最短路径算法有Dijkstra算法和Floyd(弗洛伊德算法)

历史来源

Dijkstra算法是一种计算图中单源最短路径的算法,由荷兰计算机科学家艾兹赫尔·戴克斯特拉在1956年提出。这个算法用于解决有向图中单个源点到其他各顶点的最短路径问题。

算法的基本思想是,从源点出发,逐步探索源点到其他各顶点的最短路径。算法使用了一个优先队列来维护所有待访问的顶点,并按照路径长度递增的顺序进行访问。算法执行过程中,一旦找到从源点到某个顶点的最短路径,就将这个顶点从优先队列中移除,并将这个最短路径长度作为该顶点的“标签”。

Dijkstra算法的步骤如下:

  • 初始化:将所有顶点的最短路径估计值设为无穷大,除了源点设为0。将所有顶点状态设为未访问。创建一个优先队列,并将源点加入优先队列。
  • 循环执行以下步骤直到优先队列为空: a. 从优先队列中取出具有最小估计值的顶点u。 b. 标记顶点u为已访问。 c. 对于顶点u的每一个邻接点v,执行以下操作: i. 计算通过u到达v的路径长度。 ii. 如果这个路径长度小于当前v的最短路径估计值,则更新v的最短路径估计值。 iii. 将顶点v及其新的最短路径估计值加入优先队列。
  • 算法结束,此时如果所有顶点都被访问过,那么每个顶点的最短路径估计值就是源点到该顶点的最短路径长度。

example

在这里插入图片描述

基于上图分析 Dijkstra 算法的过程,找到节点A到其他任意节点的最短路径。

  1. 首先初始化所有节点的最短距离、是否访问以及先驱节点
节点是否已访问最短路径距离先驱节点
Afalse0-
Bfalse--
Cfalse--
Dfalse--
Efalse--
Ffalse--
  1. 由于节点A到其本身的距离为0且最短,将其加入最短路径中,并标记已访问。
节点是否已访问最短路径距离先驱节点
Atrue0-
Bfalse--
Cfalse--
Dfalse--
Efalse--
Ffalse--
  1. 接下来更新经过节点A的相邻节点距离到起始节点的距离,即BA DA,同时更新B点和A点的先驱节点
节点是否已访问最短路径距离先驱节点
Atrue0-
Bfalse5A
Cfalse--
Dfalse3A
Efalse--
Ffalse--
  1. 继续选择未访问节点中拥有最短的路径距离的节点,即D点
节点是否已访问最短路径距离先驱节点
Atrue0-
Bfalse5A
Cfalse--
Dtrue3A
Efalse--
Ffalse--
  1. 更新经过节点D的相邻节点距离到起始节点的距离,即EDA,通时更新E点的先驱节点
节点是否已访问最短路径距离先驱节点
Atrue0-
Bfalse5A
Cfalse--
Dtrue3A
Efalse9D
Ffalse--
  1. 继续选择未访问节点中拥有最短的路径距离的节点,即B点
节点是否已访问最短路径距离先驱节点
Atrue0-
Btrue5A
Cfalse--
Dtrue3A
Efalse9D
Ffalse--
  1. 更新经过节点B的相邻节点距离到起始节点的距离,即CBA EBA,通时更新C点和E点的先驱节点。此时EBA这条路径更短,故进行更新。
节点是否已访问最短路径距离先驱节点
Atrue0-
Btrue5A
Cfalse7B
Dtrue3A
Efalse6B
Ffalse--
  1. 继续选择未访问节点中拥有最短的路径距离的节点,即E点
节点是否已访问最短路径距离先驱节点
Atrue0-
Btrue5A
Cfalse7B
Dtrue3A
Etrue6B
Ffalse--
  1. 更新经过节点E的相邻节点距离到起始节点的距离,判断DEBA FEBA BEDA,通时更新先驱节点。
节点是否已访问最短路径距离先驱节点
Atrue0-
Btrue5A
Cfalse7B
Dtrue3A
Etrue6B
Ffalse10E
  1. 继续选择未访问节点中拥有最短的路径距离的节点,即C点
节点是否已访问最短路径距离先驱节点
Atrue0-
Btrue5A
Ctrue7B
Dtrue3A
Etrue6B
Ffalse10E
  1. 更新经过节点C的相邻节点距离到起始节点的距离。F点经过CE到达A点距离相同,故不再变化
节点是否已访问最短路径距离先驱节点
Atrue0-
Btrue5A
Ctrue7B
Dtrue3A
Etrue6B
Ffalse10E
  1. 检查所有未标记节点中距离最短的节点F,将其加入最短路径中,并标记
节点是否已访问最短路径距离先驱节点
Atrue0-
Btrue5A
Ctrue7B
Dtrue3A
Etrue6B
Ftrue10E
  1. 至此算法结束,得到一个从源节点A到各个节点的最短距离和路径。路径集合可以通过先驱节点推导出来。例如F到A的最短路径距离为10,一步步推导得出最短路径为A - B - E - F。

标签:科研,--,路径,算法,距离,最短,访问,Dijkstra,节点
From: https://blog.csdn.net/Messiah___/article/details/137527466

相关文章

  • 归并排序,时间复杂度O(n*logn),空间复杂度O(n),是稳定算法
    空间复杂度原因是因为需要额外数组空间来进行排序时间复杂度T(n)=2T(n/2)+O(n),a=2,b=2,c=1根据master公式可知时间复杂度O(nlogN)归并排序可以排序数据量很大的数组,举例说明,例如要排序有2^64个数字的数组,那么归并排序将会开辟64层系统栈,这并不会导致栈溢出.include<stdio......
  • 最优算法100例之38-构建乘积数组
    专栏主页:计算机专业基础知识总结(适用于期末复习考研刷题求职面试)系列文章https://blog.csdn.net/seeker1994/category_12585732.html题目描述给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用......
  • 【学习笔记】dijkstra
    一、dijkstra1.定义&作用很简单。一个单源最短路算法。2.思想&实现我觉得sm的图已经够了。二、堆优化dijkstra1.先来认识一下proirity_queue2.如何使用proirity_queue对dijkstra优化?每一步,我们都需要找到\(d\)值最小的节点(即\(......
  • 常用集合算法
    算法简介:set_intersection//求两个容器的交集set_union//求两个容器的并集set_difference//求两个容器的差集一、set_intersection:求两个容器的交集函数原型:set_intersection(iteratorbeg1,iteratorend1,iteratorbeg2,iteratorend2,iteratordest);//be......
  • acwing算法全总结——搜索与图论
    acwing算法全总结——搜索与图论dfsbfs树与图的深度优先遍历树与图的广度优先遍历拓扑排序最短路问题dijkstra最短路bellman-ford最短路spfa最短路floyd最短路最小生成树prim最小生成树kruskal最小生成树二分图搜索与图论这一章算是对数据结构与算法的进阶提升吧,它......
  • 【多UAV航迹规划】基于ACO蚁群优化的多UAV航迹规划算法matlab仿真
    目录1.算法仿真效果2.MATLAB源码3.算法概述3.1ACO蚁群优化算法原理......
  • 基于PSO的NARMAX模型参数辨识算法matlab仿真
    目录1.算法仿真效果2.MATLAB源码3.算法概述4.部分参考文献1.算法仿真效果matlab2022a仿真结果如下:......
  • 某狗网歌曲接口逆向之加密算法刨析
    逆向网址aHR0cHM6Ly93d3cua3Vnb3UuY29t逆向链接aHR0cHM6Ly93d3cua3Vnb3UuY29tL21peHNvbmcvN2dxcGVzNjguaHRtbA== 逆向接口aHR0cHM6Ly93d3dhcGkua3Vnb3UuY29tL3BsYXkvc29uZ2luZm8= 逆向过程 请求方式:GET逆向参数        signature:1898d8f157837fa......
  • ROS中自定义全局算法规划器(c++)
     ros中编写一个全局路径规划器并集成为ros插件,加载到turtlebot3机器人平台上仿真验证参考资料:ROS中自定义全局规划器(上)_算法部署_哔哩哔哩_bilibili官网教程:navigation/Tutorials/WritingAGlobalPathPlannerAsPlugininROS-ROSWiki1.建立工作空间mkdir-pjps_......
  • KMP算法
    前言KMP算法:用于寻找s串中是否包含a串算法思路思路:暴力解法中使用(i,j)......