Dijkstra
Dijkstra（狄克斯特拉）算法是解决单源最短路径问题的经典算法。
简单直观的理解：
它是 “加权版的 BFS（广度优先搜索）”。
核心逻辑
- 以此为中心：指定一个起点（比如 A）。
- 贪心策略：每次从未访问的节点中，选出一个离起点当前距离最近的节点。
- 松弛操作 (Relaxation)：以此节点为跳板，检查能不能通过它，让它的邻居离起点更近。如果能，就更新邻居的距离。
- 锁定：处理完该节点后，将其标记为“已确定”，不再回头。
适用条件
- 边权非负：图中不能有负权边（如果有负权边，需用 Bellman-Ford 算法）。
Floyd-Warshall
Floyd-Warshall（弗洛伊德）算法是解决多源最短路径问题的经典算法。 简单直观的理解： 它是 “中转站（抄近道）” 策略的暴力枚举。 核心逻辑
- 上帝视角：它不再只盯着一个起点，而是同时计算图中任意两点之间的最短路径。
- 动态规划 (DP)：
- 核心拷问：“如果我经过节点 K 中转，能不能比直达（或经过旧的中转方案）更近？”
- 公式：D[i][j] = $ \min(D[i][j], \ D[i][k] + D[k][j]) $
- 三重循环：
- 第一层：尝试把节点 1 做中转，更新所有路径。
- 第二层：尝试把节点 2 做中转…
- 直到尝试完所有节点。
对比
- Dijkstra：单源（1对多）。像是在地图上从某一点扩散。复杂度 O(V^2) 或 O(E \log V)。
- Floyd：多源（多对多）。像是计算了一张完整的“里程表”。复杂度 O(V^3)，非常慢，但代码极其简单（只有5行核心代码），且支持负权边（只要没有负权环）。