最短路算法1.Dijkstra算法2.stl优先队列自定义堆3.堆优化的Dijkstra算法4.SPFA算法5.Floyd算法
1.Dijkstra算法1.1 算法流程阐释1.初始化:出发点的最短路长度置为零,其余点的最短路长度置为正无穷。2.n轮松弛:Dij算法将点分为已经求出最短路的点的集合和未求出最短路的点的集合。最终得出结果必须使未求出最短路的点的集合为空,初始时所有点都未求出最短路,因此需要N轮松弛,就是最外层循环次数。3.每轮松弛:在未求出最短路的点的集合中找到距离出发点最近的点:在未求出最短路的点的集合中找到一个到出发点的距离最近的点,把它加入已求出最短路的点的集合。4.每轮松弛:更新该点到所有未求出最