标签： 科研 -- 路径 算法 距离 最短 访问 Dijkstra 节点
Dijkstra算法是解决图论中的最短路径问题 而最短路径问题是在图中找到两个节点之间的最短路径 在导航中确定路线最短，在网络中路由器使用Dijkstra算法确定最短路径和转发端口。 最短路径算法有Dijkstra算法和Floyd（弗洛伊德算法） Dijkstra算法是一种计算图中单源最短路径的算法，由荷兰计算机科学家艾兹赫尔·戴克斯特拉在1956年提出。这个算法用于解决有向图中单个源点到其他各顶点的最短路径问题。
算法的基本思想是，从源点出发，逐步探索源点到其他各顶点的最短路径。算法使用了一个优先队列来维护所有待访问的顶点，并按照路径长度递增的顺序进行访问。算法执行过程中，一旦找到从源点到某个顶点的最短路径，就将这个顶点从优先队列中移除，并将这个最短路径长度作为该顶点的“标签”。
Dijkstra算法的步骤如下：
初始化：将所有顶点的最短路径估计值设为无穷大，除了源点设为0。将所有顶点状态设为未访问。创建一个优先队列，并将源点加入优先队列。 循环执行以下步骤直到优先队列为空： a. 从优先队列中取出具有最小估计值的顶点u。 b. 标记顶点u为已访问。 c. 对于顶点u的每一个邻接点v，执行以下操作： i. 计算通过u到达v的路径长度。 ii. 如果这个路径长度小于当前v的最短路径估计值，则更新v的最短路径估计值。 iii. 将顶点v及其新的最短路径估计值加入优先队列。 算法结束，此时如果所有顶点都被访问过，那么每个顶点的最短路径估计值就是源点到该顶点的最短路径长度。
基于上图分析 Dijkstra 算法的过程，找到节点A到其他任意节点的最短路径。
首先初始化所有节点的最短距离、是否访问以及先驱节点 节点 是否已访问 最短路径距离 先驱节点 A false 0 - B false - - C false - - D false - - E false - - F false - -
由于节点A到其本身的距离为0且最短，将其加入最短路径中，并标记已访问。 节点 是否已访问 最短路径距离 先驱节点 A true 0 - B false - - C false - - D false - - E false - - F false - -
接下来更新经过节点A的相邻节点距离到起始节点的距离，即BA DA，同时更新B点和A点的先驱节点 节点 是否已访问 最短路径距离 先驱节点 A true 0 - B false 5 A C false - - D false 3 A E false - - F false - -
继续选择未访问节点中拥有最短的路径距离的节点，即D点 节点 是否已访问 最短路径距离 先驱节点 A true 0 - B false 5 A C false - - D true 3 A E false - - F false - -
更新经过节点D的相邻节点距离到起始节点的距离，即EDA，通时更新E点的先驱节点 节点 是否已访问 最短路径距离 先驱节点 A true 0 - B false 5 A C false - - D true 3 A E false 9 D F false - -
继续选择未访问节点中拥有最短的路径距离的节点，即B点 节点 是否已访问 最短路径距离 先驱节点 A true 0 - B true 5 A C false - - D true 3 A E false 9 D F false - -
更新经过节点B的相邻节点距离到起始节点的距离，即CBA EBA，通时更新C点和E点的先驱节点。此时EBA这条路径更短，故进行更新。 节点 是否已访问 最短路径距离 先驱节点 A true 0 - B true 5 A C false 7 B D true 3 A E false 6 B F false - -
继续选择未访问节点中拥有最短的路径距离的节点，即E点 节点 是否已访问 最短路径距离 先驱节点 A true 0 - B true 5 A C false 7 B D true 3 A E true 6 B F false - -
更新经过节点E的相邻节点距离到起始节点的距离，判断DEBA FEBA BEDA，通时更新先驱节点。 节点 是否已访问 最短路径距离 先驱节点 A true 0 - B true 5 A C false 7 B D true 3 A E true 6 B F false 10 E
继续选择未访问节点中拥有最短的路径距离的节点，即C点 节点 是否已访问 最短路径距离 先驱节点 A true 0 - B true 5 A C true 7 B D true 3 A E true 6 B F false 10 E
更新经过节点C的相邻节点距离到起始节点的距离。F点经过CE到达A点距离相同，故不再变化 节点 是否已访问 最短路径距离 先驱节点 A true 0 - B true 5 A C true 7 B D true 3 A E true 6 B F false 10 E
检查所有未标记节点中距离最短的节点F，将其加入最短路径中，并标记 节点 是否已访问 最短路径距离 先驱节点 A true 0 - B true 5 A C true 7 B D true 3 A E true 6 B F true 10 E
至此算法结束，得到一个从源节点A到各个节点的最短距离和路径。路径集合可以通过先驱节点推导出来。例如F到A的最短路径距离为10，一步步推导得出最短路径为A - B - E - F。 标签： 科研 ,
-- ,
路径 ,
算法 ,
距离 ,
最短 ,
访问 ,
Dijkstra ,
节点
From： https://blog.csdn.net/Messiah___/article/details/137527466
