最短路径

• Dijkstra算法 (单源最短路径)：
  • 思想：贪心策略。按路径长度递增的次序产生最短路径。
  • 步骤*：
    1. 初始集合 $S=\{v_0\}$，距离数组 $D$ 初始为直达距离。
    2. 选出 $D$ 中最小且不在 $S$ 中的顶点 $k$，加入 $S$。
    3. 以 $k$ 为中间点，松弛（更新）其他顶点的距离：若 $D[j]>D[k]+weight(k,j)$，则更新。
  • 限制：不能处理负权边。
  • 复杂度：$O(n^2)$。
• Floyd算法 (多源最短路径)：
  • 思想：动态规划。逐个尝试将顶点 $k$ 作为中间跳板。
  • 核心公式： $D[i][j]=\min (D[i][j],D[i][k]+D[k][j])$
  • 复杂度：$O(n^3)$。