Floyd-Dijkstra-Spfa算法详解：解决ACM最短路径问题

本资源主要关注的是在算法竞赛中解决最短路径问题的几种经典方法，包括Floyd-Warshall算法、Dijkstra算法和Bellman-Ford算法的简化版SPFA（Shortest Path Faster Algorithm）。以下是详细介绍： 1. **初始化函数** (`init()`)：首先定义一个二维数组`maps`用于存储图中的边权值，其中`n`表示顶点的数量。在初始化阶段，将对角线上的元素设为0，非对角线元素设为无穷大，表示默认无边或无限距离。 2. **Floyd-Warshall算法 (`floyd()`)**：这是一种动态规划的方法，通过遍历所有中间节点来找到所有节点对之间的最短路径。算法逐层更新每条边的长度，确保了任何两点之间的路径是经过所有其他节点的最短路径。这种方法适用于没有负权重环的图。 3. **SPFA (Shortest Path Faster Algorithm) 实现 (`spfa()`)：这是一种针对有向图的优化版Dijkstra算法，适合处理带负权边的情况。它维护一个优先级队列`q`，用于存储待处理的节点。算法从起点`st`开始，设置起点的距离为0，其他节点距离为无穷大。在循环中，不断取出距离最小且未访问过的节点，更新其相邻节点的距离，并将其标记为已访问。 4. **Dijkstra算法 (`dijkstra()`)**：原生的Dijkstra算法只适用于非负权重图。在这个简化版的实现中，`dis`数组存储从起点到各节点的最短距离，`vis`数组记录节点是否已被访问。算法通过每次选取当前未访问且距离最小的节点，直到所有节点都被访问过或找到终点`ed`。 这些函数可以用来解决最短路径问题，例如在计算机竞赛中的ACM（Association for Computing Machinery）题目中，需要求解给定图中两点间的最短路径。根据实际问题的需求，可以选择Floyd-Warshall算法对于所有节点对求最短路径，或者Dijkstra和SPFA针对特定起点和终点进行路径搜索。在处理复杂图或带有负权边的情况下，SPFA通常更快，因为它允许负权边存在但不陷入无限循环。