floyed

算法来源

集合分类:

  • 任意两个的路径组成集合A
  • 集合A 按起点终点分类 Ai,jA_{i,j}
  • Ai,jA_{i,j} filter 中间经过最大点为k的最短路 : Ak,i,jA_{k,i,j}
  • Bk,i,j=⋃s=1kAs,i,jB_{k,i,j} = \bigcup_{s=1}^k A_{s,i,j} 中间经过最大点不超过k的最短路 组成的集合
  • Bk,i,jB_{k,i,j} 与 Bk−1,i,jB_{k-1,i,j} 之间的关系?
    • Bk,i,j=Bk−1,i,j∪Ak,i,jB_{k,i,j} = B_{k-1,i,j} \cup A_{k,i,j}
    • min(Bk,i,j)=min(min(Bk−1,i,j),Ak,i,j)min(B_{k,i,j}) = min( min(B_{k-1,i,j}) ,A_{k,i,j})

转移方程

f(k,i,j) 中间经过的最大点不超过k的最短路

f(k,i,j)=min{f(k−1,i,j),f(k−1,i,k)+f(k−1,k,j)} f(k,i,j) = min\{f(k-1,i,j) , f(k-1,i,k) + f(k-1,k,j) \}