Floyd-Warshall
隣接行列表現のグラフに対する推移閉包(Transitive Closure)を行う非再帰アルゴリズム.単に、任意の二つのノードが接続されているかどうかを調べる. 例えば、A→B, B→C, という辺があった場合は、A→Cというパスを求められる.
Program1(Floyd-Warshall)
void init2() {
for(int i = 0 ; i < MAX ; i++) {
for(int j = 0 ; j < MAX ; j++) {
d[i][j] = data[i][j];
}
}
}
void floyd() {
int i, j, k;
for(k = 0 ; k < n ; k++) {
for(i = 0 ; i < n ; i++) {
if(d[i][k]) {
for(j = 0 ; j < n ; j++) {
if(d[k][j] && i != j) {
if(!d[i][j] || d[i][k] + d[k][j] < d[i][j]) {
d[i][j] = d[i][k] + d[k][j];
}
}
}
}
}
}
}
EOF
** Program2(Floyd-Warshall minimax) [#hedb15fb]
#code(c)
#include
void init() {
for(int i = 0 ; i < MAX ; i++) {
for(int j = 0 ; j < MAX ; j++) {
data[i][j] = INT_MAX;
}
}
}
void func() {
for(int k = 0 ; k < MAX ; k++) {
for(int i = 0 ; i < MAX ; i++) {
for(int j = 0 ; j < MAX ; j++) {
data[i][j] = min(data[i][j], max(data[i][k], data[k][j]));
}
}
}
}