信奥赛C++提高组csp-s之Dijkstra算法详解

信奥赛C++提高组csp-s之Dijkstra算法详解1. Dijkstra算法是什么及其作用Dijkstra算法是用于解决单源最短路径问题的经典算法，由荷兰计算机科学家Edsger W. Dijkstra于1956年提出。它能够在非负权图中，找到从起点到所有其他节点的最短路径。主要作用：寻找图中单个源点到其他所有节点的最短路径适用于有向图和无向图广泛应用于网络路由、地图导航、物流规划等领域重要特性：只适用于边权值为非负的图每次确定一个节点的最短距离使用贪心策略，每次选择当前已知最短距离的节点进行扩展2. Dijkstra算法原理基本思想：将图中的节点分为两类：已确定最短路径的节点集合S和未确定最短路径的节点集合U初始时，S只包含源点，源点到自身的距离为0，到其他节点