Floyd-Warshallアルゴリズムの最上位ループ

Question

Floyd-WarshallアルゴリズムのK（最上位ループ）は何を表していますか？ 私は 'k'が中間の頂点の番号を教えてくれるか、またはKがk番目の頂点が中間の頂点として取られることを教えているのか混乱しています。

Answer 1

フロイド・ウォーシャル：

for(every vertex k that could possibly make distance from i to j shorter) 
     for(every possible vertex i) 
      for(every possible vertex j) 
       if(going through k can make the distance from i to j shorter) 
        you should go through k and update distance between i and j as you go