Dijkstra 算法

定义

Dijkstra 算法是求解带权图中单源最短路径的经典算法,由荷兰计算机科学家 Edsger W. Dijkstra 于 1956 年提出,要求所有边的权值非负。

原理

算法维护一个距离数组和已确定最短路径的顶点集合,每次从未确定集合中取出当前距离最小的顶点,将其标记为已确定,并用它松弛相邻顶点的距离。使用二叉堆等优先队列优化后,时间复杂度为 O((V+E)logV)。

应用

广泛用于网络路由协议(如 OSPF 的链路状态计算)、地图导航、游戏寻路等场景,也是 A* 等启发式搜索算法的基础。

局限

不能处理负权边,含负权时需改用 Bellman-Ford 或 SPFA 等算法;在超大规模图上通常配合双向搜索、分层预处理等技术加速。