Dijkstra 单源最短路径算法

一、算法用途Dijkstra 用于求解一个起点到图中所有其他节点的最短路径，是导航、网络路由、路径规划中最常用的算法。使用前提：图中所有边的权值 ≥ 0，不允许负权边和负环。二、核心思想算法基于贪心策略：每次从尚未确定最短路径的节点里，选出当前离起点最近的节点u，并用它去更新其邻居节点的路径长度。由于边权非负，一旦某个节点被选为 “当前最近”，它的最短路径就已经确定，后续不会再有更优路线，因此可以直接标记不再修改。三、核心操作：松弛（Relaxation）设：dist[v]表示起点到v目前已知的最短距离存在一条边u → v，长度为w如果从起点经过 u 再到 v，比当前记录的起点到 v 的距离更短，就更新dist[v]为这条更短路径的长度。if (dist[v] dist[u] + w) dist[v] = dist[u] + w;简单理解：发现更近的路，就更新路线。四、所需数据结构邻接表：存储图结构，记录每个点能到达的点及边权dist 数组：保存起点到每个点的当前最短距离vis 数组：标记节点的最短路径是否已确定