戴克斯特拉算法 戴克斯特拉算法英語Dijkstras algorithm又稱迪杰斯特拉算法Dijkstra算法是由荷兰计算机科学家艾茲赫尔戴克斯特拉在年发现的算法并于年后在期刊上发表戴克斯特拉算法使用类似廣度优先搜索的方法解决赋权图的单源最短路径问题 该算法存在很多变体戴克斯特拉的原始版本仅适用于找到两个顶点之间的最短路径后来更常见的变体固定了一个顶点作为源结点然后找到该顶点到图中所有其它结点的最短路径产生一个最短路径树 该算法解决了圖 G   V  E  displaystyle Glangle VErangle  上带权的单源最短路径问题具体来说戴克斯特拉算法设置了一顶点集合 S displaystyle S 在集合 S displaystyle S 中所有的顶点与源点 s displaystyle s 之间的最终最短路径权值均已确定算法反复选择最短路径估计最小的点 u  V  S displaystyle uin VS 并将 u displaystyle u 加入 S displaystyle S 中该算法常用于路由算法或者作为其他图算法的一个子模块举例来说如果图中的顶点表示城市而边上的权重表示城市间开车行经的距离该演算法可以用来找到两个城市之间的最短路径 应当注意绝大多数的戴克斯特拉算法不能有效处理带有负权边的图 戴克斯特拉算法在计算机科学的人工智能等领域也被称为均一开销搜索并被认为是最良优先搜索英语bestfirst search的一个特例