【科研相关知识】Dijkstra算法

• 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. 首先初始化所有节点的最短距离、是否访问以及先驱节点

1. 由于节点A到其本身的距离为0且最短，将其加入最短路径中，并标记已访问。

1. 接下来更新经过节点A的相邻节点距离到起始节点的距离，即BA DA，同时更新B点和A点的先驱节点

1. 继续选择未访问节点中拥有最短的路径距离的节点，即D点

1. 更新经过节点D的相邻节点距离到起始节点的距离，即EDA，通时更新E点的先驱节点

1. 继续选择未访问节点中拥有最短的路径距离的节点，即B点

1. 更新经过节点B的相邻节点距离到起始节点的距离，即CBA EBA，通时更新C点和E点的先驱节点。此时EBA这条路径更短，故进行更新。

1. 继续选择未访问节点中拥有最短的路径距离的节点，即E点

1. 更新经过节点E的相邻节点距离到起始节点的距离，判断DEBA FEBA BEDA，通时更新先驱节点。

1. 继续选择未访问节点中拥有最短的路径距离的节点，即C点

1. 更新经过节点C的相邻节点距离到起始节点的距离。F点经过CE到达A点距离相同，故不再变化

1. 检查所有未标记节点中距离最短的节点F，将其加入最短路径中，并标记

1. 至此算法结束，得到一个从源节点A到各个节点的最短距离和路径。路径集合可以通过先驱节点推导出来。例如F到A的最短路径距离为10，一步步推导得出最短路径为A - B - E - F。