【プレート】Floydアルゴリズムおよび経路記録
933 ワード
Floydアルゴリズム実装:距離行列を隣接行列に初期化し、3層のforサイクルを行い、パスを与えるにはpath 2次元配列を再帰すればよい.
int matrix[n][n];
int dist[n][n];
int path[n][n];
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
{
dist[i][j] = matrix[i][j];
path[i][j] = -1;
}
}
///floyd
for(int k = 0; k < n; ++k)
{
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
{
if(dist[i][j] > dist[i][k] + dist[k][j])
{
dist[i][j] = dist[i][k] + dist[k][j];
path[i][j] = k;
}
}
}
}
///
int path_[n]; path[0] = i;
int k = 1;
///k,path,path_ ,
/// ,
///
void retrieve_path(int i, int j)
{
if(i == j) return;
if(path[i][j] == -1)
path_[k++] = j;
else
{
retrieve_path(i, path[i][j]);
retrieve_path(path[i][j], j);
}
}