任意の2点間の最短経路問題(Floyd-Warshallアルゴリズム)

                            。Floyd-Warshall      
             。  ，    p={v1,v2,...vl}           p   v1  vl       ，       {v2,v3,...vl-1}    。
Floyd-Warshall      ： 
   G      V={1,2,3,...,n}，         {1,2,..,k}，   K   n   。
       i,j  V， i j             {1,2,3,...,k}   ，  p          ，      p     。Floyd-Warshall       p  i j      
    {1,3,..,k-1}          。        k     p        。
    （1）    k    p      ，   p             {1,2,...,k-1}.  ，   i   j          {1,2,...,k}       。
    （2）    k   p      ，   p     i~k,k~j。
      ，        ：
 i j      d[i][j],          ：
d[i][j]= d[i][j]         k
       = min(d[i][j],d[i][k]+d[k][j])       k                 
       min(d[i][j],d[i][k]+d[k][j]) 
      DP  ，   O(|V|3)                  。

int d[MAX_V][MAX_V]; //d[u][v]   e=(u,v)   （     INF，d[i][i]=0）
int V; //    

void floyd_warshall(){
    for(int k=0;k
        for(int i=0;i
            for(int j=0;j
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            } 
        }
    }
}