박두현의 컴퓨터 이론들 - 플로이드 알고리즘

 

안녕하세요. 건국대학교 박두현 입니다.

일전에 글을 쓰다가 잠시 놀았습니다. 많이... 그런데 이제 방학이에요. 다시 써보려구요.

주중에 선배님이자 에프에이리눅스에서 소프트웨어 개발자로 개신 효원이 형이 멀티미디어 소프트웨어 공학을 전공하는 대학생 다운 글을 한번 올려보라고 했습니다.

전 쉽게 가고 싶은데 효원이 형이 소프트웨어 공학도면 부가가치 높은걸 해야한다고 해서... ㅜ_ㅜ

막걸리 한잔과 함께 멀 써야할지 고민고민 하다가 알고리즘에 관련된 글들을 써보면 좋을 것 같다는 대선배님의 의견을 받아서요, 그렇게 해볼까 합니다. 하나도 모르는데요... ㅜ_ㅜ

 

오늘은 그 첫번째로 Floyd Alg. 에 대해서 설명할까 합니다.

학교에서 배운 그대로 한번 풀어나가 보도록 하겠습니다.

 

1. 프로이드 알고리즘(Floyd Alg.)은 무엇인가?

 

알고리즘 이름은 거의 대부분 논문 발표자의 이름을 따는 전통이 대부분이기 때문에 역시 이 알고리즘도 프로이드가 제안한 알고리즘이 되겠습니다. 용도는 최단거리 찾기 알고리즘이 되겠습니다.

보통 최단거리 알고리즘 하면 '다익스트라' 알고리즘을 생각하게 되는데요, 이 프로이드 알고리즘도 유명합니다.

 

다익스트라의 알고리즘은 시작정점 하나에 대하여 다른 모든 정점까지의 최단거리를 구하는데 사용됩니다.

각각의 모든 정점에서 다른 모든 정점까지의 최단 거리를 구하고자 한다면, 다익스트라의 알고리즘을 n번 수행함으로서 얻을 수 있습니다.

 

프로이드 알고리즘은 보다 효율성을 위해 제안되었습니다.

주어진 그래프를 구성하는 정점 사이의 간선 E(i, j)에 두 정점 사이의 거리를 나타내는 가중치를 부여 합니다.

이러한 가중치는 C(i, j) 로서 표현된다. 만일 n 개의 정점으로 이루어진 그래프를 고려한다면, 그래프를 나타내는 n*n 의 행렬 adj_matrix[][] 와 거리를 나타내는 n*n 의 행렬 dist[][] 를 구성한다.

 

2. 프로이드 알고리즘 살펴보기

 

행렬 dist[i][j] 에는 간선 E(i, j)에 부여된 가중치가 설정(i ≠ j)
만일 정점 i와 j사이에 간선이 없는 경우 ∞로 설정

 

shortest_floyd(int adj_matrix[][]) {
    dist[SIZE][SIZE];

    dist[][] = adj_matrix[][] 로 초기화
        for(k = 0; k < n; k++)
            for(i = 0; i < n; i++)
                for(j = 0; j < n; j++)
                    dist[i][j] = Min(dist[i][j], dist[i][k] + dist[k][j]);
    return(dist);
}

 

3. 분석해 보기

 

floyd_alg-1.jpg  

[프로이드 알고리즘 분석]

 

위의 그림은 플로이드의 알고리즘을 단계별로 보인 것 입니다.

플로이드의 알고리즘을 보면 k 값이 n 번 변화되는 동안 i 와 j 의 모든 경우가 아래의 식에 대하여 고려되죠. 즉 아래의 식은 n3 번 반복되는 것으로 볼 수 있습니다. 따라서 시간복잡도는 O(n3) 가 됩니다.

 

dist[i][j] = Min(dist[i][j], dist[i][k] + dist[k][j]);

 

위 식은 모든 정점간의 거리를 저장한 행렬식의 값을 각 단계별로 변화를 시켜 모든 정점들 사이의 최단거리 값을 계산하는데 사용됩니다. 즉, 정점 i 와 j 사이의 거리값을 정점 k 를 거쳐서 갈 때의 거리와 비교하여 보다 적은 값을 지속적으로 반영함으로써 최종적으로 남은 값이 각 정점들 간의 최단거리 값이 되도록 합니다.

 

예를 들어, k = 0 일 때,

dist[0][3] = Min(dist[0][3], dist[0][1] + dist[1][3]);
-> dist[0][3] = Min(∞, 3+6); 이 되고
-> dist[0][3] = 9;

k=i 일 때에는 정점 i 를 거치는 경로이므로 i 행과 i 열의 값은 전 단계와 변동이 없습니다.

 

4. 마치면서...

 

알고리즘은 역시 어렵네요.

어렵지만 간지나는 글을 올려보라는 선배의 압박에 그래도 올려 봅니다. 공부했던 건데 다시 보니까 새롭기도 하네요.

다음번엔 또 어떤 알고리즘을 올려야 할 까 많이많이 고민됩니다.

다음 시간에도 재미있는 알고리즘으로 찾아뵙겠습니다~

 

이 게시물을...