最短路径

原文oi wiki:SP

基础

1.Dijkstra
2.Floyd

1.Dijkstra

用于求 单源最短路径，只能处理非负权边。其核心思想是： 每次从未确定的点中选择当前距离源点最近的点加入集合，并用它来更新其他点的最短距离。 原理十分简单，大学课堂100%讲过 堆优化 Dijkstra 时间复杂度为 O((n + m)log n),适用于稀疏图