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]);
}