一、最短路径算法（Shortest Path）

最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。

最短路径不一定是经过边最少的路径，但在这些最短路径中，长度最短的那一条路径上只有一条边，且它的权值在从源点出发的所有边的权值最小。

算法具体的形式包括：

• 确定起点的最短路径问题：也叫单源最短路问题，即已知起始结点，求最短路径的问题。
• 确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
• 确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。
• 全局最短路径问题：也叫多源最短路问题，求图中所有的最短路径。

用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：Dijkstra算法、A*算法、Bellman-Ford算法、SPFA算法（Bellman-Ford算法的改进版本）、Floyd-Warshall算法、Johnson最短路算法。

二、迪杰斯特拉（Dijkstra）算法

迪杰斯特拉（Dijkstra）算法是由荷兰计算机科学家艾兹赫尔·韦伯·迪杰斯特拉（Edsger Wybe Dijkstra），又译艾兹赫尔·韦伯·戴克斯特拉于1959年提出的，因此又叫戴克斯特拉。

Dijkstra 算法是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

1. 算法思想

迪杰斯特拉算法的主要思想是通过不断更新顶点之间的最短路径，逐步找到从指定起点到各个顶点的最短路径。该算法以贪心策略为基础，在每一步选择当前最优的顶点，并根据该顶点更新其他顶点的距离值，确保已确定的最短路径不再被修改。通过反复进行这样的选择和更新，最终得到了从起点到所有其他顶点的最短路径。

总的来说，迪杰斯特拉算法的思想就是以逐步迭代的方式，通过不断选择当前最优的顶点，更新其他顶点的距离值，直至得到起点到各个顶点的最短路径。

2. 算法步骤

1. 初始化：创建一个集合 Q 存放未确定最短路径顶点，初始包含所有顶点；创建一个集合 S 存放所有已知实际最短路径值的顶点，初始为空；创建一个数组 dist 存放最短距离数组，记录每个顶点到起点的最短距离，初始值都为无穷大，起点的距离为0。
2. 选取起点：从集合 Q 中选取一个离起点距离最短的顶点，将其移动到集合 S 中。
3. 更新距离：对于当前确定最短路径的顶点，遍历其所有相邻顶点，如果通过当前顶点到达相邻顶点的距离小于相邻顶点当前记录的最短距离，则更新相邻顶点的最短距离为新的距离值，更新完相邻顶点的最短距离后，将这些顶点从集合 Q 移动到集合 S 。
4. 重复步骤2和步骤3，直到集合 Q 为空。
5. 最终得到起点到每个顶点的最短路径。

三、弗洛伊德（Frolyd）算法

弗洛伊德（Floyd-Warshall，Floyd ）算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德（Robert W. Floyd）命名。

Floyd 算法以动态规划为基础，该算法通过不断更新顶点之间的最短路径长度，以找到任意两个顶点之间的最短路径长度。

1. 算法思想

弗洛伊德算法的算法思想是通过动态规划的方式来求解图中所有点对之间的最短路径。该算法的核心思想是利用一个中间顶点集合，逐步缩小这个集合的规模，更新并维护每对顶点之间的最短路径长度。

具体而言，弗洛伊德算法通过多次迭代，尝试在已知顶点之间的最短路径基础上，考虑添加一个新的中间顶点后是否可以缩短路径长度。如果存在更短的路径，就更新当前已知的最短路径长度；否则保持原状。不断重复这个过程，最终得到所有点对之间的最短路径长度矩阵。

弗洛伊德算法的动态规划思想在于利用已知的最短路径信息来推导出更长路径的最短路径，通过不断更新和迭代，最终得到所有顶点之间的最短路径长度。

2. 算法步骤

1. 初始化：创建一个二维数组 distance，其中 distance[i][j] 表示顶点 i 到顶点 j 的最短路径长度。将 distance[i][j] 初始化为连接顶点 i 和 j 的边的权重。如果不存在直接相连的边，则将 distance[i][j] 初始化为无穷大。

2. 更新最短路径：对于每对顶点 i 和 j，遍历所有顶点 k，比较通过顶点 k 是否可以使顶点 i 到 j 的路径变得更短，即检查 distance[i][k] + distance[k][j] 是否小于当前已知的 distance[i][j]。如果是，则更新 distance[i][j] = distance[i][k] + distance[k][j]。

3. 重复更新：重复执行步骤2，直到所有顶点对之间的最短路径长度都被计算出来。

4. 检查负权回路：如果存在负权回路，即顶点到自身的距离小于0，说明图中存在无限可减小的路径长度，算法将无法正常运行。

5. 最终得到所有点对之间的最短路径长度矩阵。

四、最短路径算法对比

如果遇到单源且边为正数，直接Dijkstra。
至于 使用朴素版还是 堆优化版 还是取决于图的稠密度， 多少节点多少边算是稠密图，多少算是稀疏图，这个没有量化，如果想量化只能写出两个版本然后做实验去测试，不同的判题机得出的结果还不太一样，一般情况下，可以直接用堆优化版本。

如果是遇到多源点求最短路，直接 Floyd。