Warshall 알고리즘

Warshall 알고리즘은 그래프에서

한 노드에서 다른 노드까지의 도달 가능성을 알아보는 알고리즘이다.

시간복잡도는 O(n^3)이다.

이 알고리즘은 인접 행렬을 사용한다.

위의 그래프를 인접 행렬로 나타내면

위의 표와 같다.

위 표는 다음과 같이 해석한다.

표[x, y]  :  (x행 y열), x 노드에서 y노드로 진행 가능함을 뜻함

ex) 1노드에서 3노드로 진행 가능, 1노드에서 5노드로 진행 불가

이 표에 warshall 알고리즘을 적용하면 다음과 같이 나타낼 수 있다.

1 노드에서는 3, 4, 5 노드로 진행 가능하며

2 노드에서는 1, 3, 4, 5 노드로 진행 가능하며

3 노드는 어느 노드로도 진행 할 수 없고

4 노드는 오직 5 노드로만 진행 가능하며

5 노드는 어느 노드로도 진행 할 수 없음을 뜻한다.

알고리즘을 대략적으로 설명하면

x -> y로의 진행이

x -> y로의 직접적인 진행이 가능하거나

x -> k -> y로의 우회적인 진행이 가능한지를 살펴보는 것이다.

덜 대략적으로 설명하면

초기 인접행렬을 M0라고 하고

M1을 x에서 y로 하나의 노드를 경유하는 경우라고 놓으면

M1[x, y] 는 M0[x, y]가 1이면 다른 노드를 경유하지 않고도 x에서 y로 갈 수 있음을 말하고

M0[x, k]와 M0[k, y]가 1이면 k 노드를 경유하여 x에서 y로 갈 수 있음을 말한다.

이걸 m0에서 m(n-1)까지

반복하면

x에서 노드를 0~n-1개 경유하여 y로 갈 수 있는지를 알 수 있다.

따라서 프로그램적으로 적어보면

M[x][y] = M[x][y] | (M[i][k] & M[k][j])

로 나타낼 수 있다.

함수를 쓰면 다음과 같다.

void warshall()

{

int i, j, k;

for (k = 0; k < n; ++k)

{

for (i = 1; i <=n; ++i)

{

for (j = 1; j <=n; ++j)

{

ar[i][j] = ar[i][j] | (ar[i][k + 1] & ar[k + 1][j]);

}

}

}

}

이 알고리즘과 관련하여 풀 수 있는 문제들...

키 순서(초4)/koi_stature

구슬 찾기/bead