求Floyd-Warshall算法优化技巧：固定部分顶点仅计算三个顶点

不存在适用于所有场景的通用技巧，能让你在第一遍遍历后跳过部分固定顶点、仅计算剩余三个顶点。但在特定约束条件下，你可以做针对性的简化，以下是具体分析：

核心逻辑限制 #

Floyd-Warshall的核心是动态规划：依次将每个顶点k作为中间中转点，更新所有顶点对(i,j)的最短路径。跳过任意k的遍历，意味着你默认这个顶点不可能成为任何i-j路径的最优中转点——这在大多数通用场景下不成立，跳过会导致部分最短路径无法被正确计算。

可优化的特殊场景 #

如果你的场景满足以下任一条件，可以跳过指定顶点的计算：

• 隔离性约束：被忽略的两三个顶点与剩余三个顶点之间没有有效路径（比如边权为无穷大，或无连接边），它们不可能成为这三个顶点两两之间路径的中转点。
• 路径确定性约束：业务逻辑或图的拓扑结构保证，剩余三个顶点之间的最短路径绝不会经过那几个固定顶点（比如分属不同子图，或中转路径权值必然大于直接路径）。

在这些情况下，你可以仅将剩余三个顶点作为中间点k，遍历更新这三个顶点之间的两两路径，无需处理其他顶点。

更高效的替代方案 #

如果你的目标只是计算某三个顶点之间的两两最短路径，完全不需要跑完整的Floyd-Warshall：

• 若图中无负权边，对每个目标顶点跑一次Dijkstra算法，时间复杂度会远低于完整的Floyd-Warshall。
• 若存在负权边，可对每个目标顶点跑Bellman-Ford算法，同样比修改Floyd-Warshall更直接。

内容的提问来源于stack exchange，提问作者Akhil