P 103任意の2点間の最短問題Floyd_warshallアルゴリズム

1927 ワード

//            Floyd-Warshall  
//   0~k, i,j    ,i j     ;
/*
d[k][i][j]  d[k-1][i][j] **G[i][k]  **G[k][j]        G[k][i] G[j][k]
d[k-1][i][k]  d[k-1][k][j]
*/
d[k][i][j]=min(d[k-1][i][j],d[k-1][i][k]+d[k-1][k][j]);

///int G[MAX_V][MAX_V];
///            
///DP             
int d[MAX_V][MAX_V];

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